Phân Cụm Ảnh Khuôn Mặt Sử Dụng Mạng Nơ Ron Đồ Thị

Khóa luận tốt nghiệp nghiên cứu tốt nghiệp khoa học máy tính phân cụm ảnh khuôn mặt sử dụng mạng nơ ron đồ thị phân cấp, vận dụng lý thuyết vào thực tế, đề xuất giải pháp cụ thể

• Tác giả: Phạm Đỗ Hoàng My
• Người hướng dẫn: TS. Mai Tiến Dũng
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Phân Cụm Ảnh Khuôn Mặt Sử Dụng Mạng Nơ Ron Đồ Thị
• Loại tài liệu: khóa luận tốt nghiệp
• Năm xuất bản: 2023
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Giới thiệu bài toán
• 1.2. Tổng quan
• 1.3. Mô tả bài toán
• 1.4. Ứng dụng
• 1.5. Mục tiêu khóa luận
• 1.6. Đóng góp khóa luận
• 1.7. Cấu trúc Khóa luận tốt nghiệp
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ CÁC NGHIÊN CỨU LIÊN QUAN
• 2.1. Các kiến thức cơ sở
• 2.2. Mạng nơron đồ thị
• 2.3. Stochastic Gradient Descent
• 2.4. Mini-batch Gradient Descent
• 2.5. Các hướng tiếp cận
• 2.5.1. Phân cụm phân vùng
• 2.5.2. Phân cụm phân cấp
• 2.5.3. Phân cụm theo phổ
• 3. CHƯƠNG 3: HƯỚNG TIẾP CẬN TRONG KHÓA LUẬN
• 3.1. Tổng quan kiến trúc các mạng nơ-ron đồ thị phân cấp
• 3.2. Quá trình lọc cạnh
• 3.3. Quá trình tổng hợp đặc trưng
• 3.4. Tính toán ma trận
• 4. CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 4.1. Môi trường và ngôn ngữ cài đặt
• 4.2. Phương pháp đánh giá
• 4.3. Tập dữ liệu thực nghiệm
• 4.3.1. Tập dữ liệu Hannah
• 4.4. Kết quả thực nghiệm
• 4.4.1. Kết quả trên tập dữ liệu cũ
• 4.4.2. Kết quả trên các tập dữ liệu khác
• 4.5. Hướng phát triển
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phân Cụm Ảnh Khuôn Mặt Sử Dụng Mạng Nơ Ron Đồ Thị

Phân cụm ảnh khuôn mặt là một lĩnh vực nghiên cứu quan trọng trong công nghệ nhận diện khuôn mặt. Với sự phát triển của công nghệ, việc phân tích và xử lý hình ảnh khuôn mặt đã trở nên dễ dàng hơn. Mạng nơ ron đồ thị (GNN) là một trong những phương pháp tiên tiến giúp cải thiện độ chính xác trong việc phân cụm các hình ảnh khuôn mặt. Bài viết này sẽ đi sâu vào các khía cạnh của phân cụm ảnh khuôn mặt và ứng dụng của mạng nơ ron đồ thị.

1.1. Khái Niệm Về Phân Cụm Ảnh Khuôn Mặt

Phân cụm ảnh khuôn mặt là quá trình nhóm các hình ảnh có khuôn mặt tương tự nhau vào cùng một cụm. Điều này giúp dễ dàng quản lý và truy xuất thông tin từ các bức ảnh lớn. Việc sử dụng các thuật toán học sâu như mạng nơ ron đồ thị giúp cải thiện hiệu quả phân cụm.

1.2. Tầm Quan Trọng Của Mạng Nơ Ron Đồ Thị

Mạng nơ ron đồ thị cung cấp một cách tiếp cận mới trong việc phân tích dữ liệu không có nhãn. Bằng cách sử dụng cấu trúc đồ thị, các mối quan hệ giữa các điểm dữ liệu có thể được khai thác để cải thiện độ chính xác của việc phân cụm khuôn mặt.

II. Thách Thức Trong Phân Cụm Ảnh Khuôn Mặt

Mặc dù có nhiều tiến bộ trong công nghệ phân cụm, nhưng vẫn tồn tại nhiều thách thức. Một trong những vấn đề lớn nhất là sự đa dạng của khuôn mặt và sự thiếu hụt dữ liệu có nhãn. Điều này dẫn đến khó khăn trong việc áp dụng các mô hình đã học trên các tập dữ liệu khác nhau.

2.1. Đa Dạng Khuôn Mặt

Khuôn mặt của mỗi người có thể thay đổi theo nhiều yếu tố như ánh sáng, góc chụp và biểu cảm. Điều này làm cho việc phân cụm trở nên khó khăn hơn, vì các mô hình cần phải nhận diện được những biến thể này.

2.2. Thiếu Dữ Liệu Có Nhãn

Nhiều bộ dữ liệu khuôn mặt không có nhãn, điều này gây khó khăn trong việc huấn luyện các mô hình. Việc thiếu dữ liệu có nhãn làm giảm độ chính xác của các thuật toán phân cụm.

III. Phương Pháp Phân Cụm Ảnh Khuôn Mặt Bằng Mạng Nơ Ron Đồ Thị

Phương pháp sử dụng mạng nơ ron đồ thị để phân cụm ảnh khuôn mặt đã cho thấy nhiều hứa hẹn. Bằng cách kết hợp các đặc trưng của khuôn mặt và cấu trúc đồ thị, các mô hình có thể học được cách phân cụm hiệu quả hơn.

3.1. Cấu Trúc Mạng Nơ Ron Đồ Thị

Cấu trúc của mạng nơ ron đồ thị cho phép các nút trong đồ thị tương tác với nhau, từ đó cải thiện khả năng phân tích và nhận diện khuôn mặt. Điều này giúp tăng cường độ chính xác trong việc phân cụm.

3.2. Quy Trình Phân Cụm

Quy trình phân cụm bao gồm ba bước chính: nhận diện khuôn mặt, trích xuất đặc trưng và phân cụm. Mỗi bước đều quan trọng để đảm bảo rằng các khuôn mặt tương tự được nhóm lại với nhau.

IV. Ứng Dụng Thực Tiễn Của Phân Cụm Ảnh Khuôn Mặt

Phân cụm ảnh khuôn mặt có nhiều ứng dụng trong thực tiễn, từ an ninh đến quản lý dữ liệu. Việc tự động phân nhóm các bức ảnh khuôn mặt giúp tiết kiệm thời gian và tài nguyên.

4.1. Ứng Dụng Trong An Ninh

Trong lĩnh vực an ninh, việc phân cụm ảnh khuôn mặt giúp nhận diện và theo dõi các đối tượng trong thời gian thực. Điều này rất quan trọng trong việc đảm bảo an toàn công cộng.

4.2. Ứng Dụng Trong Quản Lý Dữ Liệu

Phân cụm ảnh khuôn mặt cũng có thể được sử dụng trong quản lý dữ liệu, giúp tổ chức và tìm kiếm thông tin một cách hiệu quả hơn. Điều này đặc biệt hữu ích trong các hệ thống lưu trữ lớn.

V. Kết Luận Và Tương Lai Của Phân Cụm Ảnh Khuôn Mặt

Phân cụm ảnh khuôn mặt sử dụng mạng nơ ron đồ thị là một lĩnh vực đầy tiềm năng. Với sự phát triển không ngừng của công nghệ, các phương pháp mới sẽ tiếp tục được nghiên cứu và cải tiến.

5.1. Tương Lai Của Nghiên Cứu

Nghiên cứu trong lĩnh vực này sẽ tiếp tục mở rộng, với nhiều ứng dụng mới và cải tiến trong các thuật toán phân cụm. Điều này sẽ giúp nâng cao độ chính xác và hiệu quả trong việc nhận diện khuôn mặt.

5.2. Thách Thức Cần Giải Quyết

Mặc dù có nhiều tiến bộ, nhưng vẫn còn nhiều thách thức cần phải giải quyết, bao gồm việc cải thiện độ chính xác và khả năng áp dụng của các mô hình trên các tập dữ liệu khác nhau.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Sự phát triển của công nghệ thu nhận hình ảnh hiện đại từ hệ thống máy quay giám sát an ninh, điện thoại thông minh và máy tính xách tay đã dẫn đến sự bùng nổ của khối lượng dữ liệu ảnh khuôn mặt số hóa. Trong các hệ thống giám sát an ninh phục vụ cơ quan điều tra và doanh nghiệp, một đoạn phim có thể chứa hàng nghìn khung hình với số lượng khuôn mặt rất lớn và đa dạng. Việc rà soát, xác định danh tính khuôn mặt của từng đối tượng bằng phương pháp thủ công đòi hỏi nguồn nhân lực lớn và tiêu tốn nhiều thời gian. Do đó, nhu cầu tự động hóa quy trình trích xuất và phân nhóm dữ liệu ảnh khuôn mặt theo danh tính cá nhân trở thành bài toán có ý nghĩa thực tiễn cấp bách.

Trong lĩnh vực học máy, phân cụm là bài toán thuộc nhóm học không giám sát, xử lý dữ liệu đầu vào không được gán nhãn sẵn nhằm phân chia các đối tượng có mức độ tương đồng cao vào cùng một cụm và các đối tượng khác biệt vào các cụm khác nhau. Bài toán phân cụm khuôn mặt là bài toán nhánh chuyên biệt, tập trung vào đối tượng là ảnh chứa khuôn mặt người. Hai ứng dụng thực tế tiêu biểu của bài toán này bao gồm:

1. Tự động gom nhóm tập hợp hình ảnh khuôn mặt khi không có nhãn liên kết bên ngoài để phục vụ công tác quản lý và truy xuất dữ liệu sau này.
2. Tự động gán nhãn cho những bức ảnh khuôn mặt mới xuất hiện vào các cụm danh tính sẵn có trong hệ thống.

Thách thức cốt lõi đặt ra trong bối cảnh thực tế là bài toán nhận diện tập mở (Open Set Recognition - OSR). Dữ liệu khuôn mặt ngoài đời thực luôn biến động và không có bất kỳ bộ dữ liệu nào chứa trọn vẹn danh tính của tất cả mọi người. Các phương pháp phân cụm truyền thống thường chỉ được huấn luyện và đánh giá trên cùng một phân phối dữ liệu khép kín. Khi đối mặt với các danh tính hoàn toàn mới, các mô hình này buộc phải tái phân cụm từ đầu, đồng thời đòi hỏi người lập trình phải tinh chỉnh thủ công các tham số ràng buộc (như số lượng cụm $k$, ngưỡng khoảng cách, hay tâm cụm). Điều này làm tiêu tốn tài nguyên tính toán và hạn chế khả năng tổng quát hóa. Do đó, yêu cầu nghiên cứu đặt ra là xây dựng một phương pháp có khả năng học điều kiện hội tụ trực tiếp từ dữ liệu, cho phép phân cụm chính xác các đối tượng thuộc các lớp danh tính chưa từng xuất hiện trong tập huấn luyện.

Mô tả bài toán theo mô hình toán học:

• Đầu vào (Input):
  • Tập $T$: Các vector đặc trưng của tập ảnh khuôn mặt dùng để huấn luyện, đã được phân vào $k$ cụm định danh.
  • Tập $E$: Các vector đặc trưng của tập ảnh khuôn mặt cần gom cụm kiểm thử, trong đó số lượng cụm và nhãn danh tính của từng ảnh chưa được xác định trước.
• Đầu ra (Output): Các vector đặc trưng thuộc tập $E$ được gom chính xác thành $n$ cụm tương ứng với danh tính thực tế.

Mục tiêu và nhiệm vụ nghiên cứu:

• Mục tiêu: Nắm vững và làm chủ phương pháp gom cụm khuôn mặt dựa trên mạng nơ-ron đồ thị phân cấp kết hợp mạng nơ-ron tích chập đồ thị, hỗ trợ xác định số lượng người xuất hiện trong dữ liệu camera và phục vụ truy vết thông tin đối tượng.
• Nhiệm vụ nghiên cứu (gồm 3 nội dung thực hiện):
  1. Nội dung 1 - Khảo sát các hướng tiếp cận liên quan: Tìm hiểu toàn diện các phương pháp phân cụm thuộc nhóm có giám sát, không giám sát và bán giám sát nhằm nhận diện ưu thế và sự khác biệt của mạng nơ-ron đồ thị.
  2. Nội dung 2 - Nghiên cứu chuyên sâu phương pháp lựa chọn: Khảo cứu lý thuyết mô hình HILANDER, phân tích mã nguồn thuật toán, tiến hành huấn luyện và kiểm thử trên dữ liệu gốc của bài báo cũng như mở rộng thực nghiệm trên các bộ dữ liệu mới; điều chỉnh các siêu tham số mô hình để phân tích độ ổn định và ưu nhược điểm.
  3. Nội dung 3 - Đánh giá thực nghiệm và hoàn thiện khóa luận: Tổng hợp kết quả định lượng, so sánh với các thuật toán nền tảng, đề xuất hướng phát triển và hoàn thiện báo cáo khóa luận tốt nghiệp.

Đối tượng và phạm vi nghiên cứu:

• Đối tượng nghiên cứu: Ảnh có chứa khuôn mặt người (quy định mỗi ảnh chỉ chứa duy nhất một khuôn mặt) và mô hình mạng nơ-ron đồ thị (Graph Neural Network - GNN).
• Phạm vi nghiên cứu: Giới hạn trên các bộ dữ liệu ảnh khuôn mặt công khai; tập trung vào giai đoạn gom cụm các vector đặc trưng khuôn mặt đã được trích xuất bằng các mô hình học sâu; áp dụng kiến trúc mạng nơ-ron đồ thị phân cấp HILANDER. Nghiên cứu tập trung vào bước thứ ba trong quy trình ba bước (Nhận diện khuôn mặt $\rightarrow$ Trích xuất đặc trưng $\rightarrow$ Phân cụm khuôn mặt). Thời gian thực hiện đề tài từ ngày 05/09/2022 đến ngày 12/01/2023 tại Trường Đại học Công nghệ Thông tin - ĐHQG-HCM, bảo vệ trước Hội đồng theo Quyết định số 155/QĐ-ĐHCNTT ngày 01/03/2023.

Cơ sở lý thuyết và phương pháp

Khóa luận thiết lập nền tảng lý thuyết vững chắc dựa trên sự giao thoa giữa lý thuyết đồ thị hình thức, kiến trúc học sâu trên đồ thị, các giải thuật tối ưu hóa phi tuyến và các trường phái phân cụm dữ liệu kinh điển.

Về lý thuyết đồ thị, đồ thị được định nghĩa là cấu trúc dữ liệu $G = (V, E)$, trong đó $V$ là tập hợp các đỉnh (nodes/vertices) khác rỗng và $E$ là tập hợp các cạnh (edges) kết nối giữa các cặp đỉnh. Các khái niệm hình thức được tác giả chuẩn hóa bao gồm:

• Đỉnh kề và khuyên (loop): Hai đỉnh $v_i, v_j \in V$ được gọi là kề nhau nếu tồn tại cạnh $e_m \in E$ nối giữa chúng. Cạnh nối một đỉnh với chính nó được gọi là khuyên.
• Phân loại đồ thị: Đơn đồ thị (chỉ có tối đa một cạnh nối giữa hai đỉnh và không chứa khuyên), đa đồ thị (tồn tại nhiều cạnh cùng kết nối một cặp đỉnh), giả đồ thị (đồ thị có chứa khuyên), đồ thị có hướng (các cạnh có thứ tự điểm đầu và điểm cuối) và đồ thị vô hướng (các cạnh không phân biệt thứ tự).
• Đồ thị con và tính liên thông: Đồ thị con $G'$ được tạo thành bằng cách loại bỏ một số đỉnh hoặc cạnh từ đồ thị gốc $G$. Đồ thị liên thông là đồ thị không thể phân rã thành hợp của các đồ thị con rời rạc.
• Bậc của đỉnh: Trong đồ thị vô hướng, bậc của đỉnh $v$ ký hiệu là $\deg(v)$, biểu thị số cạnh liên thuộc với $v$ (mỗi khuyên đóng góp 2 bậc). Tổng bậc của tất cả các đỉnh bằng hai lần số cạnh: $\sum_{v \in V} \deg(v) = 2|E|$. Trong đồ thị có hướng, bậc của đỉnh phân tách thành bậc vào $\deg^-(v)$ (số cạnh hướng vào $v$) và bậc ra $\deg^+(v)$ (số cạnh đi ra từ $v$), thỏa mãn $\sum \deg^-(v) = \sum \deg^+(v) = |E|$.
• Biểu diễn đồ thị bằng ma trận: Sử dụng ma trận kề $A \in \mathbb{R}^{n \times n}$ với phần tử $a_{ij} = 1$ khi có cạnh nối và $a_{ij} = 0$ khi không có cạnh nối; ma trận liên thuộc $B \in \mathbb{R}^{n \times m}$ biểu diễn quan hệ giữa đỉnh và cạnh (trong đồ thị có hướng, $b_{ij} = -1$ nếu cạnh đi ra, $b_{ij} = 1$ nếu cạnh đi vào).

Về kiến trúc mạng nơ-ron đồ thị (GNN), mô hình xử lý dữ liệu phi cấu trúc lưới thông qua ba thành phần: tập đỉnh $V$, tập cạnh $E$ và ma trận đặc trưng nút $H$. Trong khi mạng nơ-ron tích chập (CNN) chỉ giới hạn trên dữ liệu lưới có cấu trúc đều đặn, mạng tích chập đồ thị (Graph Convolutional Network - GCN) thực hiện nhân ma trận đặc trưng $H$ với ma trận kề $A$ để lan truyền và tổng hợp thông tin từ các đỉnh lân cận: $$H^{(l+1)} = \sigma(A H^{(l)} W^{(l)})$$ Đối với mạng chú ý đồ thị (Graph Attention Network - GAT), ma trận kề được thay thế bằng ma trận trọng số chú ý nhằm định lượng mức độ quan trọng khác nhau giữa các nút lân cận. Khóa luận phân tích các mô hình phân cụm đồ thị đi trước như LGCN, GCN-V và GCN-V+E, chỉ ra rằng các mô hình này chỉ sử dụng một tầng đồ thị duy nhất, dẫn đến hạn chế trong việc khái quát hóa và không đáp ứng được yêu cầu phân cụm tập mở khi nhãn dữ liệu kiểm thử hoàn toàn khác biệt với tập huấn luyện.

Về các thuật toán tối ưu hóa, khóa luận khảo sát có hệ thống các biến thể của thuật toán Gradient Descent:

• Batch Gradient Descent (BGD): Tính toán đạo hàm của hàm mất mát trên toàn bộ dữ liệu huấn luyện, đảm bảo hội tụ ổn định về cực tiểu nhưng tiêu tốn tài nguyên và thời gian với dữ liệu lớn.
• Stochastic Gradient Descent (SGD): Cập nhật tham số dựa trên đạo hàm của từng mẫu dữ liệu đơn lẻ, giảm chi phí tính toán nhưng gây dao động mạnh quanh điểm cực trị.
• Mini-batch Gradient Descent: Cân bằng hai phương pháp trên bằng cách tính toán gradient trên một lô dữ liệu nhỏ (thường từ 16 đến 256 mẫu).
• Các biến thể nâng cao: Khảo sát Momentum SGD, Nesterov Accelerated Gradient (NAG), AdaGrad (tự động điều chỉnh tốc độ học dựa trên tổng bình phương gradient quá khứ), RMSprop.
• Thuật toán Adam (Adaptive Moment Estimation): Kết hợp ưu điểm của RMSprop và Momentum. Adam ước lượng thời điểm thứ nhất (trung bình động $m_t$) và thời điểm thứ hai (phương sai không tập trung $v_t$) của gradient $g_t$: $$m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t$$ $$v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2$$ Triệt tiêu sai lệch khởi tạo ban đầu thông qua các giá trị hiệu chỉnh: $$\hat{m}_t = \frac{m_t}{1 - \beta_1^t}, \quad \hat{v}t = \frac{v_t}{1 - \beta_2^t}$$ Cập nhật tham số mô hình theo công thức: $$\theta{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t$$

Về các trường phái phân cụm truyền thống:

• Phân cụm phân vùng (K-means): Phân phối dữ liệu vào $k$ cụm dựa trên khoảng cách tới các tâm điểm; nhược điểm lớn là phụ thuộc nghiêm ngặt vào việc khởi tạo tâm ban đầu và phải biết trước số lượng cụm $k$.
• Phân cụm phân cấp (Hierarchical Clustering): Xây dựng sơ đồ cây (dendrogram) theo hướng tổng hợp (Agglomerative - từ dưới lên) hoặc phân chia (Divisive - từ trên xuống); ưu điểm là không cố định số cụm nhưng kết quả phụ thuộc vào điều kiện liên kết (linkage).
• Phân cụm theo phổ (Spectral Clustering): Gồm 3 bước: xây dựng đồ thị tương đồng $k$-NN, biến đổi không gian bằng vector riêng của ma trận Laplacian, và áp dụng thuật toán phân cụm truyền thống (K-means) trên không gian mới.
• Phân cụm dựa trên mật độ (DBSCAN, DENCLUE): Gom cụm dựa trên mật độ điểm lân cận cao ở vùng lõi và phân tách bằng vùng thưa, hỗ trợ lọc điểm nhiễu nhưng suy giảm hiệu quả khi dữ liệu quá dày đặc hoặc mật độ phân bổ không đồng đều.

Phương pháp nghiên cứu thực tế được triển khai là phương pháp thực nghiệm kết hợp mô hình học sâu. Tác giả sử dụng các vector đặc trưng khuôn mặt $F = {f_i}{i=1}^N$ được trích xuất từ tập ảnh đầu vào $D = {I_i}{i=1}^N$. Mô hình phân cụm chính được nghiên cứu là mạng nơ-ron đồ thị phân cấp HILANDER. Phương pháp này xây dựng đồ thị lân cận $k$-NN, thực hiện lọc cạnh dựa trên khả năng liên kết và mật độ nút, sau đó gom các thành phần liên thông để tạo thành đồ thị thô hơn ở tầng tiếp theo. Quá trình này diễn ra phân cấp đa tầng, trong đó mô hình tích hợp dự đoán đồng thời độ liên kết cạnh và mật độ đỉnh nhằm tối ưu hóa thời gian thực thi.

Nguồn dữ liệu thực nghiệm được lấy từ các bộ dữ liệu khuôn mặt quy chuẩn:

• Tập kiểm thử Test-IMDB-SameDist.
• Tập dữ liệu diễn viên phim Hannah.
• Tập dữ liệu ảnh người nổi tiếng IMDB (chứa dữ liệu hình ảnh của các nhân vật công chúng như Lady Gaga, Quinn Cummings).

Nội dung chính theo từng chương

Chương 1: Tổng quan

Chương 1 mở đầu bằng việc định nghĩa bài toán phân cụm không giám sát và bài toán phân cụm khuôn mặt. Tác giả làm rõ quy trình 3 giai đoạn xử lý dữ liệu khuôn mặt và xác định trọng tâm nghiên cứu tập trung vào giai đoạn thứ ba: phân cụm các vector đặc trưng đại diện cho khuôn mặt mà không can thiệp vào giai đoạn nhận diện vị trí và trích xuất đặc trưng. Thách thức nhận diện tập mở (OSR) được phân tích như một rào cản chính đối với các mô hình hiện nay, đặt ra yêu cầu phải có một giải thuật có khả năng khái quát hóa sang các phân phối danh tính chưa từng thấy trong quá trình học. Chương này thiết lập mô hình toán học cho đầu vào $T, E$ và đầu ra $n$ cụm, chỉ ra hai ứng dụng thực tiễn trong công tác quản lý dữ liệu an ninh, xác định ba mục tiêu nghiên cứu và công bố bố cục năm chương của khóa luận.

Chương 2: Cơ sở lý thuyết và các nghiên cứu liên quan

Chương 2 cung cấp hệ thống cơ sở toán học và lý thuyết thuật toán cho toàn bộ đề tài. Tác giả trình bày chi tiết lý thuyết đồ thị từ các định nghĩa hình thức (đỉnh, cạnh, khuyên, đơn đồ thị, đa đồ thị, đồ thị con, tính liên thông, bậc đỉnh vô hướng và có hướng) đến các phương thức biểu diễn bằng ma trận kề $A$ và ma trận liên thuộc $B$. Phần mạng nơ-ron đồ thị đi sâu vào cơ chế hoạt động của GNN, phân tích phép nhân ma trận tích chập của GCN và ma trận trọng số chú ý của GAT, đồng thời đánh giá nhược điểm của các cấu trúc GNN đơn tầng (LGCN, GCN-V, GCN-V+E). Tác giả dành dung lượng lớn để phân tích 8 giải thuật tối ưu hóa đạo hàm, trình bày chi tiết công thức toán học và ưu nhược điểm của BGD, SGD, Mini-batch GD, Momentum, NAG, AdaGrad, RMSprop và Adam. Phần cuối chương phân loại và đối sánh 4 trường phái phân cụm: phân vùng (K-means), phân cấp (Agglomerative, Divisive), phân cụm theo phổ (Spectral Clustering) và phân cụm dựa trên mật độ (DBSCAN, DENCLUE).

Chương 3: Hướng tiếp cận trong khóa luận

Chương 3 trình bày chi tiết kiến trúc và cơ chế vận hành của mô hình mạng nơ-ron đồ thị phân cấp HILANDER:

• Tổng quan kiến trúc: Tiếp nhận tập dữ liệu $N$ ảnh khuôn mặt $D = {I_i}{i=1}^N$ cùng các vector đặc trưng tương ứng $F = {f_i}{i=1}^N$. Mô hình xây dựng một chuỗi các tầng GNN phân cấp, trong đó đồ thị ở tầng sau được tạo thành từ việc gộp các đỉnh của tầng trước.
• Quá trình lọc cạnh: Dựa trên đồ thị $k$-NN ban đầu (với $k=4$ theo minh họa), mô hình tiến hành lọc bỏ các cạnh kết nối yếu dựa trên xác suất liên kết dự đoán, phân rã đồ thị thành các thành phần liên thông rời rạc.
• Quá trình tổng hợp đặc trưng: Các đỉnh thuộc cùng một thành phần liên thông ở tầng $l$ được hợp nhất thành một siêu đỉnh (super-node) ở tầng $l+1$. Đặc trưng của siêu đỉnh mới được tổng hợp từ các đỉnh thành phần, giúp các nút lân cận gia tăng độ tương đồng biểu diễn qua từng cấp độ phân cấp.
• Tích hợp dự đoán liên kết và mật độ: Thay vì sử dụng hai mô hình độc lập để dự đoán khả năng liên kết cạnh và mật độ đỉnh như các nghiên cứu GNN trước đây, kiến trúc HILANDER kết hợp dự đoán song song hai yếu tố này trong cùng một mạng, giúp loại bỏ việc phụ thuộc vào ngưỡng hội tụ thủ công và tăng tốc độ xử lý.
• Tính toán mất mát: Trình bày công thức hàm mất mát giám sát quá trình huấn luyện nhằm tối ưu hóa việc phân tách cụm và giữ vững tính kết nối nội cụm.

Chương 4: Thực nghiệm và đánh giá

Chương 4 tập trung kiểm chứng hiệu năng mô hình trên các điều kiện thực nghiệm cụ thể:

• Môi trường và ngôn ngữ cài đặt: Thiết lập môi trường thực nghiệm với các thư viện học sâu hỗ trợ đồ thị trên nền tảng ngôn ngữ Python.
• Phương pháp đánh giá: Sử dụng các thang đo định lượng chuẩn mực bao gồm độ đo Thông tin Tương hỗ Chuẩn hóa (Normalized Mutual Information - NMI) và độ đo BCubed (gồm BCubed Precision, BCubed Recall và BCubed F-score), kết hợp việc đo lường thời gian thực thi (runtime).
• Tập dữ liệu thực nghiệm: Thử nghiệm trên 3 tập dữ liệu gồm Test-IMDB-SameDist, Hannah và IMDB. Tác giả cung cấp số liệu mô tả về số lượng ảnh, số danh tính và phân phối dữ liệu trong Bảng 4.1, kèm hình ảnh trực quan của các diễn viên (như Lady Gaga, Quinn Cummings trong tập IMDB và các mẫu trích xuất từ tập Hannah).
• Kết quả thực nghiệm và đối sánh: Phân tích kết quả định lượng được tổng hợp trong các bảng dữ liệu:
  • Bảng 4.2 ghi nhận kết quả đánh giá các phương pháp trên tập Test-IMDB-SameDist qua 3 độ đo.
  • Bảng 4.3 ghi nhận kết quả đánh giá đối sánh trên hai tập dữ liệu độc lập Hannah và IMDB.
  • Bảng 4.4 so sánh chi tiết thời gian chạy giữa các thuật toán phân cụm truyền thống và các kiến trúc dựa trên đồ thị.

Chương 5: Kết luận và hướng phát triển

Chương 5 tóm tắt các kết quả đạt được của khóa luận trong việc giải quyết bài toán phân cụm khuôn mặt tập mở bằng mạng nơ-ron đồ thị phân cấp. Tác giả khẳng định tính hiệu quả của cơ chế học điều kiện hội tụ tự động từ dữ liệu và khả năng duy trì độ chính xác cao trên các tập dữ liệu chưa từng thấy trong quá trình huấn luyện. Đồng thời, chương này chỉ ra các hạn chế còn tồn đọng và đề xuất các hướng nghiên cứu mở rộng trong tương lai.

Kết quả và đóng góp

Khóa luận đã tổng hợp các kết quả thực nghiệm định lượng chi tiết nhằm chứng minh tính ưu việt của phương pháp mạng nơ-ron đồ thị phân cấp HILANDER so với các phương pháp phân cụm kinh điển và các kiến trúc GNN đơn tầng.

Dưới đây là bảng tổng hợp các bộ dữ liệu và cấu trúc thực nghiệm được ghi nhận trong văn bản khóa luận:

Tên bộ dữ liệu	Đặc điểm đối tượng	Vai trò trong thực nghiệm	Phạm vi đánh giá
Test-IMDB-SameDist	Ảnh khuôn mặt phân phối chuẩn	Kiểm thử cơ bản	Đánh giá độ chính xác phân cụm trên 3 độ đo
Hannah	Ảnh khuôn mặt diễn viên	Kiểm thử tập mở (OSR)	Đánh giá khả năng tổng quát hóa trên tập dữ liệu mới
IMDB	Ảnh người nổi tiếng (Lady Gaga, Quinn Cummings...)	Kiểm thử tập mở (OSR)	Đánh giá độ chính xác và đo lường thời gian chạy

Kết quả thực nghiệm trên các tập dữ liệu khẳng định:

• Các phương pháp phân cụm truyền thống (K-means, phân cụm phân cấp, DBSCAN) thể hiện sự suy giảm hiệu năng rõ rệt khi đối mặt với dữ liệu tập mở do phụ thuộc vào các tham số cố định và không có khả năng thích ứng với phân phối biểu diễn phức tạp của vector đặc trưng khuôn mặt.
• Các mô hình đồ thị đơn tầng (LGCN, GCN-V, GCN-V+E) tuy cải thiện mối liên kết giữa các đỉnh lân cận nhưng thiếu cơ chế trừu tượng hóa đa cấp độ, dẫn đến việc khó xác định chính xác ranh giới cụm khi kích thước tập dữ liệu gia tăng.
• Mô hình mạng nơ-ron đồ thị phân cấp HILANDER đạt kết quả vượt trội trên cả 3 độ đo đánh giá (NMI, BCubed Precision, BCubed F-score) trên các tập kiểm thử Test-IMDB-SameDist, Hannah và IMDB (theo Bảng 4.2 và Bảng 4.3 trong văn bản).
• Về mặt thời gian thực thi (Bảng 4.4), việc tích hợp dự đoán song song độ liên kết cạnh và mật độ đỉnh trong cùng một kiến trúc giúp HILANDER đạt tốc độ tính toán nhanh hơn đáng kể so với các phương pháp GNN sử dụng hai mô hình tách biệt.

Các đóng góp khoa học chính do tác giả tự xác định bao gồm:

1. Khảo sát hệ thống hóa: Nghiên cứu và tổng hợp toàn diện các phương pháp phân cụm áp dụng cho bài toán phân cụm khuôn mặt, từ các giải thuật học máy truyền thống, phương pháp dựa trên phổ, phương pháp dựa trên mật độ cho đến các kiến trúc mạng nơ-ron đồ thị hiện đại.
2. Thực nghiệm so sánh đa chiều: Cài đặt và thực nghiệm các phương pháp đã khảo sát trên cùng một hệ quy chiếu dữ liệu, cung cấp cái nhìn định lượng khách quan về ưu nhược điểm của từng nhóm thuật toán.
3. Kiểm chứng năng lực nhận diện tập mở (OSR): Đánh giá thành công mô hình mạng nơ-ron đồ thị phân cấp trên các tập dữ liệu kiểm thử hoàn toàn mới (Hannah, IMDB), chứng minh khả năng tổng quát hóa của giải thuật khi phân cụm các danh tính chưa từng xuất hiện trong tập huấn luyện mà không cần tái cấu hình tham số.

Hạn chế và hướng nghiên cứu tiếp

Khóa luận chỉ rõ các giới hạn kỹ thuật và phạm vi nghiên cứu thực tế như sau:

• Giới hạn tiền xử lý dữ liệu: Đề tài chỉ tập trung chuyên sâu vào bước thứ ba trong quy trình xử lý khuôn mặt (phân cụm vector đặc trưng), không giải quyết bài toán định vị (face detection) và trích xuất đặc trưng (feature extraction). Dữ liệu đầu vào bắt buộc phải là các bức ảnh đã được cắt chuẩn hóa, chứa duy nhất một khuôn mặt người.
• Sự phụ thuộc vào biểu diễn đặc trưng: Hiệu quả phân cụm của đồ thị phân cấp phụ thuộc mật thiết vào chất lượng của các vector đặc trưng đầu vào do mô hình học sâu đi trước cung cấp. Nếu vector đặc trưng không đủ tính phân tách, đồ thị $k$-NN khởi tạo ban đầu sẽ chứa nhiều cạnh nhiễu, ảnh hưởng trực tiếp đến chất lượng của các tầng liên thông kế tiếp.

Các hướng phát triển tiếp theo được tác giả đề xuất bao gồm:

• Mở rộng thử nghiệm mô hình trên các bộ dữ liệu khuôn mặt có quy mô lớn hơn, độ phức tạp cao hơn về góc nghiêng, biểu cảm và điều kiện ánh sáng thực tế.
• Nghiên cứu cơ chế tối ưu hóa kết hợp giữa việc trích xuất đặc trưng khuôn mặt và phân cụm đồ thị phân cấp theo cơ chế đầu-cuối (end-to-end).
• Tinh chỉnh kiến trúc nhằm nâng cao hơn nữa tốc độ thực thi, hướng tới triển khai thử nghiệm trên các luồng video giám sát an ninh trực tuyến theo thời gian thực.

Giá trị tham khảo

Bản khóa luận tốt nghiệp là tài liệu học thuật có giá trị tham khảo thiết thực cho các nhóm đối tượng:

• Sinh viên và học viên chuyên ngành Khoa học Máy tính, Trí tuệ Nhân tạo và Thị giác Máy tính: Cung cấp tài liệu tổng hợp chuẩn mực về toán học rời rạc ứng dụng (lý thuyết đồ thị), cơ chế tích chập trên đồ thị (GCN, GAT) và bản chất toán học của 8 thuật toán tối ưu hóa đạo hàm phổ biến.
• Người làm nghiên cứu về phân cụm dữ liệu và nhận diện tập mở (Open Set Recognition): Cung cấp phương pháp luận chi tiết về việc kết hợp phân cụm phân cấp với mạng nơ-ron đồ thị nhằm giải quyết bài toán phân cụm dữ liệu không gán nhãn quy mô lớn.
• Phần nội dung có giá trị tham khảo cao nhất: Chương 2 (phần hệ thống hóa các thuật toán tối ưu hóa đạo hàm và phân loại 4 trường phái phân cụm) và Chương 3 (thiết kế chi tiết quy trình lọc cạnh, tổng hợp đặc trưng tầng và kiến trúc phân cấp của mô hình HILANDER).

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

1. Bài toán phân cụm khuôn mặt trong khóa luận được mô tả toán học với đầu vào và đầu ra như thế nào?
Bài toán nhận đầu vào gồm hai tập hợp: tập $T$ chứa các vector đặc trưng khuôn mặt huấn luyện đã được phân chia vào $k$ cụm định danh sẵn, và tập $E$ chứa các vector đặc trưng khuôn mặt kiểm thử cần gom cụm mà chưa biết trước số lượng cụm cũng như nhãn danh tính. Đầu ra của bài toán là toàn bộ các vector đặc trưng thuộc tập $E$ được phân chia chính xác vào $n$ cụm tương ứng với từng cá nhân.

2. Tại sao các mô hình GNN đơn tầng như LGCN, GCN-V hay GCN-V+E lại gặp hạn chế trong bài toán phân cụm khuôn mặt tập mở?
Các phương pháp như LGCN, GCN-V và GCN-V+E chỉ xây dựng một tầng đồ thị duy nhất để xử lý quan hệ giữa các nút dữ liệu. Cấu trúc đơn tầng này không có khả năng tổng quát hóa dữ liệu đa cấp độ, khiến mô hình bị phụ thuộc chặt chẽ vào cấu trúc của tập huấn luyện và không thể phân cụm chính xác trên các bộ dữ liệu kiểm thử có danh tính mới hoàn toàn khác biệt.

3. Kiến trúc mạng nơ-ron đồ thị phân cấp HILANDER cải tiến quy trình phân cụm như thế nào so với các phương pháp truyền thống?
Thay vì dựa vào các điều kiện dừng hoặc ngưỡng khoảng cách do người dùng tự cài đặt thủ công, HILANDER tự học điều kiện hội tụ trực tiếp từ dữ liệu. Mô hình tạo ra chuỗi đồ thị phân cấp, trong đó các siêu đỉnh ở tầng sau được tổng hợp từ các thành phần liên thông ở tầng trước. Đồng thời, mô hình tích hợp dự đoán song song cả độ liên kết cạnh và mật độ đỉnh trong cùng một mạng để tăng tốc độ tính toán.

4. Thuật toán tối ưu hóa Adam trong Chương 2 sử dụng các đại lượng nào để cập nhật tham số mô hình?
Thuật toán Adam kết hợp cơ chế của Momentum và RMSprop, tính toán hai đại lượng trung bình động gồm: trung bình động của gradient ($m_t$, ước lượng thời điểm thứ nhất) và trung bình động của bình phương gradient ($v_t$, ước lượng thời điểm thứ hai). Sau khi triệt tiêu sai lệch ban đầu thành $\hat{m}_t$ và $\hat{v}_t$, Adam cập nhật tham số mô hình $\theta$ theo tỷ lệ $\frac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t$.

5. Những bộ dữ liệu và thang đo nào được sử dụng để đánh giá thực nghiệm trong khóa luận?
Khóa luận thực nghiệm trên 3 bộ dữ liệu: tập kiểm thử chuẩn Test-IMDB-SameDist, tập ảnh diễn viên Hannah và tập ảnh người nổi tiếng IMDB. Hiệu năng của các mô hình được định lượng qua độ đo Thông tin Tương hỗ Chuẩn hóa (Normalized Mutual Information - NMI), độ đo BCubed (gồm Precision, Recall và F-score), cùng việc đo lường thời gian thực thi (runtime).

Kết luận

Khóa luận tốt nghiệp của sinh viên Phạm Đỗ Hoàng My và Nguyễn Minh Phú đã giải quyết bài toán phân cụm ảnh khuôn mặt tập mở thông qua phương pháp mạng nơ-ron đồ thị phân cấp HILANDER. Đề tài xây dựng cơ sở lý thuyết vững chắc về đồ thị, mạng GNN và các thuật toán tối ưu hóa phi tuyến, đồng thời làm rõ quy trình phân cấp đa tầng kết hợp dự đoán song song mật độ đỉnh và liên kết cạnh. Kết quả thực nghiệm trên các bộ dữ liệu quy chuẩn khẳng định mô hình có khả năng học điều kiện hội tụ tự động, đạt độ chính xác cao và tối ưu hóa thời gian thực thi khi xử lý các danh tính hoàn toàn mới ngoài tập huấn luyện.

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

Chương 1 TỔNG QUAN Tóm tắt Trong chương này chúng tôi sẽ giới thiệu về bài toán phân cụm nói chung và phân cụm khuôn mặt nói riêng cũng như những thách thức của bài toán mà chúng tôi sẽ phải giải quyết. Bên cạnh đó, chúng tôi cũng sẽ nói về mục tiêu mà chúng tôi hướng tới khi thực hiện đề tài "Phân cụm ảnh khuôn mặt sử dụng mạng nơ-ron đô thị phân cấp". Cuối cùng, chúng tôi sẽ tóm tat câu trúc tổng thể của khóa luận. 11 Giới thiệu bài toán Phân cụm là bài toán xử lý dữ liệu không được gán nhãn.

Các dữ liệu này sẽ được phân vào các cụm sao cho những dit liệu tương đồng nhau sẽ thuộc cùng một cụm, khác nhau thì khác cụm. Từ tập dữ liệu không có nhãn, để biết được tập dữ liệu này có tương đồng nhau hay không ta có thể sử dụng các độ đo tương đồng hoặc khoảng cách (Cosine, Euclidean,. Sau đó, dựa vào ngưỡng và điều kiện để hai dữ liệu được coi là tương đồng đã xác định trước để tiến hành phân chia các dtr liệu vào các cum. Sau quá trình phân cụm, dữ liệu trong cùng một cum sẽ có cùng nhãn [20].

TONG QUAN 2 Khóa luận của chúng tôi sẽ chọn tập trung vào nghiện cứu một bài toán con của phân cụm, đó là phân cụm khuôn mặt. Bài toán này tập trung vào đối tượng là ảnh khuôn mặt của con người (ảnh có chứa khuôn mặt). Kết quả của phân cụm khuôn mặt là ảnh của cùng một người thì sẽ cùng một cụm (hình[1. Quá trình phân cụm khuôn mặt sẽ gồm 3 bước: 1.

Nhận điện khuôn mặt: Định vị được khuôn mặt trong các bức ảnh. Trích xuất đặc trưng: Đưa khuôn mặt vừa tìm được về dạng các vector đặc trưng (những vector này sẽ chỉ chứa những đặc trưng quan trọng nhất của các khuôn mặt này, giúp chúng ta không cần phải xét toàn bộ khuôn mặt, bước này cũng giúp chúng ta khái quát hóa được khuôn mặt vì cho dù là ảnh khuôn mặt của cùng một người nhưng nếu xét toàn bộ khuôn mặt thì vẫn sẽ có vài điềm khác, bước này sẽ giúp chúng ta giảm bớt rủi ro khác biệt về hai khuôn mặt của cùng một người). Phân cụm khuôn mặt: phân các vector đặc trưng đó thành từng cụm, sau khi có được cụm thì các ảnh có vector đặc trưng thuộc cùng một cum sẽ có cùng một nhãn, khác cụm thì khác nhãn. Trong khóa luận này, chúng tôi chỉ tập trung vào bước thứ 3 đó là phân cụm khuôn mặt.

Trong thực tế, không một bộ dữ liệu nào chứa hết toàn bộ khuôn mặt của tất cả mọi người trên thé giới. Các bộ dữ liệu khuôn mặt có thể khác nhau một phan hoặc hoàn toàn. Điều này có liên quan đền van dé nhận diện tập mở (Open Set Recognition - OSR [29] [10]). Các phương pháp phân cum hiện tại chủ yếu chỉ làm việc trên một tập nhất định nào đó nên sẽ khó có thể áp dụng một phương pháp đã được học trên tập này cho tập khác.

Nếu có tập dữ liệu mới thì phải phân cụm lại từ đầu. Mặt khác, mỗi lần phân cụm, ta lại phải xác định điều kiện phân cụm, tham số tối ưu của bộ dữ liệu đó. Chúng ta sẽ phải tiêu tồn nhiều tài nguyên và công sức cho mỗi lần như vậy. Chính vì thế, chúng ta cần một phương pháp không chỉ phân cụm được dữ liệu thuộc các lớp đã biết trong quá trình huấn luyện mà hơn thế nữa, từ kết quả phân cum mà học được cách để có thể phân cụm những dir liệu thuộc các lớp khác những lớp đã có trong tập dữ liệu học.

Đồng thời, phương pháp này còn có thể học được điều kiện hội tụ từ chính dữ liệu mà không cần người lập trình phải cài đặt. Mô tả bài toán: ¢ Input: — T: Các vector đặc trưng của tập ảnh khuôn mặt để huấn luyện đã được phân vào k cụm. — E: Các vector đặc trưng của tập ảnh khuô n mặt cần được gom cụm, số cum và nhãn của từng ảnh chưa được biết. s Output: Các vector đặc trưng trong tập E được gom thành n cụm.

TỔNG QUAN 4 Phân cụm khuôn mặt có rất nhiều ứng dụng trong đời sống và đây là hai ứng dụng tiêu biểu nhất: s Ung dung 1: Tự động phân các bức ảnh vào các cụm. Trong thực tế, dữ liệu khuôn mặt vô cùng lớn, các dữ liệu này được thu thập từ các camera giám sát, ảnh chup,. Việc có thể gom cụm ảnh của cùng một người lại có thể giúp chúng ta dễ dàng truy vấn khi muốn tìm kiếm ảnh một người nào đó (Hnh[L1). s Ung dụng 2: Gan nhãn các ảnh khuôn mặt vào các cụm đã có.

Khi chúng ta có những bức ảnh khuôn mặt mới, thay phải tự tay tìm ra định danh của những bức ảnh mới này, mô hình phân cụm có thể giúp chúng ta (Hình[1.2 Mục tiêu khóa luận * Tìm hiểu và khảo sát các phương pháp có thể giải quyết được thách thức của bài toán đưa ra. ® Nghiên cứu về các thuật toán phân cụm khuôn mặt đã công bố, đặc biệt là các thuật toán có sử dụng mạng nơ-ron đồ thị.3 Đóng góp khóa luận ® Khảo sát và nghiên cứu một sỐ phương pháp phân cụm đã được công bồ cho bài toán phân cụm khuôn mặt. ¢ Thực nghiệm các nghiên cứu đã khảo sát trên cùng tập dữ liệu để so sánh hiệu quả giữa các phương pháp. ¢ Thử nghiệm phương pháp chính trên tập dữ liệu mới để kiểm chứng phương pháp đó có thể dùng cho các tập dữ liệu khác nhau được không.4 Câu trúc Khóa luận tot nghiệp Nội dung Khóa luận tốt nghiệp được tổ chức như sau: ¢ Chương ii} Giới thiệu về bài toán phân cụm khuôn mặt, đặc biệt là phân cụm tập mở (học tập này nhưng huấn luyện tập khác), một số ứng dụng khi giải quyết bài toán này, mục tiêu làm khóa luận, những gì đã đóng góp và cấu trúc tổng thể của khóa luận.

° Chương} Tổng quan về cơ sở lý thuyết để thực hiện bài toán và các hướng tiếp cận đã tìm hiểu được. s Chương BỊ Trình bày chỉ tiết hướng tiếp cận chính để giải quyết bài toán phân cụm khuôn mặt. TỔNG QUAN 6 s Chương 4 Trình bày môi trường thực nghiệm, các tập dữ liệu đã được dùng, phương pháp đánh giá và kết quả thực nghiệm. s Chương) BỊ Tổng kết nội dung của khóa luận và những hướng phát triển Sau này.

Chương 2 CƠ SỞ LÝ THUYET VÀ CÁC NGHIÊN CỨU LIÊN QUAN Tóm tắt Trong chương này, chúng tôi sẽ nói về cơ sở lý thuyết của những cầu trúc được sử dụng trong hướng tiếp cận chính. Đồng thời, chúng tôi cũng giới thiệu về những phương pháp phân cụm đã nghiên cứu, và nêu ra những ưu nhược điểm của các phương pháp này.1 Các kiến thức cơ sở 2.1 Lý thuyết đồ thil] Đồ thị (Graph) là một câu trúc dữ liệu gồm một tập các đỉnh V (ver- tice/node) khác rỗng và một tập các cạnh E (edge) nối giữa hai đỉnh, hai đỉnh thuộc hai đầu của cạnh có thể có thứ tự hoặc không có thứ tự. Một đồ thị G có thể được kí hiệu như sau: 1Các định nghĩa, khái niệm trong phan ly thuyết dé thị được trích dẫn và tham khảo tr (431) 29 Chương 2. CƠ SỞ LÝ THUYẾT VA CÁC NGHIÊN CUU LIEN QUAN 8 G=(V,E) Hai đỉnh „ø; với i = 1,2,.|V| được nối bởi cạnh em với m = 1,2,.|E| được gọi là hai đỉnh kê nhau.

Nếu 0¡ = 9; thì cạnh nối giữa hai đỉnh này sẽ được gọi là một vòng (loop) và đỉnh này khi đó sẽ kể với chính bản thân đỉnh đó.1: Trong đồ thi nay, ta có đỉnh A và B được nồi với nhau bởi một cạnh nỗi nên A kể với B, tương tự như vậy, B với C cũng kể nhau. Do A và C không có cạnh nổi nên A không ké C. A có thêm một vòng nên A sẽ kể với chính A. Giữa 2 đỉnh có thể có nhiều cạnh nồi, dé thị chỉ có 1 cạnh nối giữa hai đỉnh và không có vòng được gọi là don do thi.

Đồ thị mà có nhiều cạnh cùng nối hai đỉnh được gọi là đa đô thi. Đồ thị có chứa vòng được gọi là giả dé thị] D6 thị v6 hướng là đồ thị gồm tập đỉnh khác rỗng và tập các cặp cạnh nối giữa hai đỉnh không phân biệt thứ tự. Cạnh nối giữa hai đỉnh u và w có kí hiệu là uw (hoặc wu) (Hình 2. D6 thị có hướng là đồ thị gồm tập đỉnh khác rỗng và tập các cặp cạnh nồi giữa hai đỉnh có phân biệt thứ tự.

Cạnh nồi từ đỉnh u đến đỉnh w có kí hiệu là ib (Hình|2. ?Theo một số tác giả, giả đô thị và đa dé thị có ý nghĩa tương tự nhau Chương 2. CƠ SỞ LÝ THUYẾT VA CÁC NGHIÊN CUU LIEN QUAN 9 °° HINH 2.2: Đồ thịG = (V,E) cóV = {A,B,C} và E = (AB, 5c), ABE BÀ xà BC = CB. „®e LAN BÀ Cải, ab ¿ BÀ.

Ta có thể tạo ra dé thị con của một đồ thị G bằng cách loại bỏ cạnh hoặc đỉnh của G (Hình}2.4: Đồ thi G sau khi loại bỏ đỉnh A và E cùng với các cạnh AB, AE, EC, ED, EF, ta được dé thị con G’ Chương 2. CƠ SỞ LÝ THUYẾT VÀ CÁC NGHIÊN CUU LIEN QUAN 10 Hai đồ thi Gị = (VỊ, Ei) và Gy = (V2, Ez) có thể kết hợp với nhau để tạo thành một đồ thị với tập đỉnh bằng Vị U W2 và tập cạnh bằng E¡ U Ey. Nếu một đồ thị có thể được biểu diễn bằng cách hợp các dé thị lại với nhau thì đồ thị đó là đô thị không liên thông, ngược lại là đô thị liên thông (Minh họa ở hình|2.5: Đồ thi G; là dé thị liên thông vì không thé tìm được các dé thị có thể hợp thành dé thị Gị. Trong khi đó với đồ thị Gp, ta có thể biểu diễn G› bằng hai đỏ thị.

Bậc của đỉnh * Đối với đồ thị vô hướng: Bậc của một đỉnh v là số cạnh nói đến đỉnh đó] ký hiệu là deg(v). Tổng bậc của các đỉnh trong đồ thị luôn là số chan và bằng 2 lần số cạnh vì mỗi cạnh có 2 đầu nên mỗi khi tính bậc 3vì là dé thị vô hướng nên số cạnh nói đến 1 đỉnh cũng chính là số cạnh di ra từ đỉnh đó Chương 2. CƠ SỞ LÝ THUYẾT VÀ CÁC NGHIÊN CỨU LIÊN QUAN 11 của đỉnh, cạnh nói 2 đỉnh sẽ được tính 2 lần. Mỗi vòng được tính là 2 bậc.