Tổng quan luận án

Đề tài luận án tiến sĩ "Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM" do nghiên cứu sinh Nguyễn Thế Cường thực hiện dưới sự hướng dẫn khoa học của PGS. Huỳnh Thế Phùng, bảo vệ tại Trường Đại học Khoa học, Đại học Huế năm 2023, thuộc ngành Khoa học máy tính, mã số 9.01.

Tính cấp thiết của luận án xuất phát từ thực tiễn phân loại mẫu trong học máy có giám sát. Thuật toán máy véc-tơ hỗ trợ (Support Vector Machine - SVM) do Vapnik đề xuất là một công cụ phân loại mẫu chuẩn mực nhờ việc xác định siêu phẳng phân lớp tối ưu thông qua bài toán quy hoạch toàn phương lồi. Tuy nhiên, khi dữ liệu trong thực tế có cấu trúc phức tạp—trong đó mỗi lớp bao gồm nhiều cụm dữ liệu phân tán, các cụm có xu hướng phân phối khác nhau và số lượng phần tử không đồng đều—cách tiếp cận truyền thống sử dụng một siêu phẳng duy nhất của SVM hoặc hai siêu phẳng của các biến thể hiện hành bộc lộ rõ hạn chế. Khoảng trống nghiên cứu được tác giả xác định là: các biến thể SVM hiện có chưa khai thác đầy đủ thông tin cấu trúc nội tại của từng cụm dữ liệu cũng như thông tin về số lượng điểm dữ liệu trong mỗi cụm, dẫn đến việc suy giảm độ chính xác phân loại hoặc làm tăng thời gian huấn luyện mô hình khi giải các bài toán quy hoạch toàn phương kích thước lớn.

Mục tiêu nghiên cứu của luận án được xác định cụ thể như sau:

  1. Nghiên cứu, đề xuất các phương pháp mới nhằm nâng cao hiệu năng phân lớp dữ liệu (bao gồm độ chính xác phân loại và thời gian huấn luyện) đối với tập dữ liệu có cấu trúc phức tạp trên cơ sở cải tiến thuật toán SVM.
  2. Thiết lập cơ chế khai thác đồng thời thông tin cấu trúc hình học của từng cụm dữ liệu (thông qua ma trận hiệp phương sai) và thông tin về số lượng điểm dữ liệu của mỗi cụm trong các lớp.
  3. Xây dựng các thuật toán tối ưu hóa tương ứng dựa trên phương pháp giải bài toán đối ngẫu Lagrange hoặc phương pháp bình phương tối thiểu để đưa bài toán quy hoạch toàn phương phức tạp về các bài toán quy mô nhỏ hơn hoặc giải hệ phương trình tuyến tính.

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

  • Đối tượng nghiên cứu: Các thuật toán học máy và bài toán phân lớp dữ liệu có giám sát.
  • Phạm vi nghiên cứu: Tập trung vào bài toán phân loại nhị phân đối với dữ liệu đa cấu trúc, phức tạp, trong đó mỗi lớp chứa nhiều cụm dữ liệu có phân phối và số lượng phần tử khác nhau; thực nghiệm kiểm chứng được tiến hành trên tập dữ liệu giả lập không gian hai chiều và các bộ dữ liệu chuẩn từ kho dữ liệu UCI (University of California, Irvine).

Tổng quan tài liệu và vị trí của luận án

Trong quá trình phát triển các kỹ thuật phân loại dữ liệu, thuật toán SVM tiêu chuẩn (Vapnik, 1995) thiết lập siêu phẳng phân cách có lề cực đại giữa hai lớp dữ liệu thông qua bài toán quy hoạch toàn phương lồi kết hợp phương pháp nhân tử Lagrange. Nhằm khắc phục các hạn chế về chi phí tính toán và khả năng mở rộng của SVM tiêu chuẩn, nhiều biến thể đã được công bố:

  • SVM xấp xỉ (PSVM - Proximal Support Vector Machine) của Mangasarian và Musicant (2001) tìm kiếm hai siêu phẳng song song bao quanh hai lớp dữ liệu bằng cách thay đổi ràng buộc bất đẳng thức thành ràng buộc đẳng thức, chuyển bài toán tối ưu về việc giải một hệ phương trình tuyến tính duy nhất. Tuy nhiên, việc cố định hai siêu phẳng song song làm hạn chế khả năng thích ứng hình học.
  • SVM xấp xỉ qua các trị riêng suy rộng (GEPSVM) của Mangasarian và Wild (2006) đề xuất tìm hai siêu phẳng không nhất thiết song song bằng cách giải hai bài toán tìm trị riêng suy rộng từ thương Rayleigh không ràng buộc. Điểm hạn chế của GEPSVM là độ chính xác và khả năng mở rộng chưa ổn định trên các tập dữ liệu thực nghiệm lớn.
  • SVM song sinh (TSVM) của Jayadeva, Khemchandani và Chandra (2007) xác định hai siêu phẳng không song song bằng cách giải hai bài toán quy hoạch toàn phương đối ngẫu kích thước nhỏ hơn bài toán gốc của SVM tiêu chuẩn. TSVM giảm độ phức tạp tính toán xấp xỉ 4 lần so với SVM thông thường nhưng vẫn đòi hỏi giải bài toán quy hoạch toàn phương có ràng buộc.
  • SVM song sinh dùng bình phương tối thiểu (LSTSVM) của Kumar và Gopal (2009) kết hợp nguyên lý của TSVM với kỹ thuật bình phương tối thiểu, thay thế hoàn toàn các ràng buộc bất đẳng thức bằng đẳng thức, cho phép tìm hai siêu phẳng thông qua giải hai hệ phương trình tuyến tính, giúp rút ngắn thời gian huấn luyện.
  • SVM song sinh có cấu trúc (S-TSVM) của Qi và cộng sự (2013) tích hợp thuật toán phân cụm liên kết của Ward (1963) để đưa thông tin ma trận hiệp phương sai của từng cụm dữ liệu vào hàm mục tiêu của TSVM, ép các siêu phẳng định hướng dọc theo các cụm.

Bên cạnh đó, tác giả cũng điểm lại các hướng nghiên cứu liên quan như: xử lý dữ liệu không cân bằng trong SVM (Akbani và cộng sự, 2004; Batuwita và Palade, 2010), giảm độ phức tạp tính toán (Collobert và Bengio, 2001; Keerthi và cộng sự, 2001), các kỹ thuật trích chọn đặc trưng và giảm chiều dữ liệu (Bi và cộng sự, 2003), cùng các phát triển gần đây như thuật toán SVM có trọng số (Bao và cộng sự, 2019) hay mô hình TS-WRSVM (Mo và cộng sự, 2021).

Khoảng trống nghiên cứu mà luận án lựa chọn giải quyết: Mặc dù S-TSVM đã chú ý tới cấu trúc cụm, song mô hình này vẫn duy trì việc phân chia bằng hai siêu phẳng duy nhất cho toàn bộ hai lớp và chưa tính đến trọng số số lượng mẫu của từng cụm. Khi dữ liệu có độ phân tán cao, số lượng cụm lớn và kích thước cụm không đều, việc chỉ dùng hai siêu phẳng không đủ bao quát biên phân lớp. Luận án định vị nghiên cứu vào việc thiết lập các chiến lược phân tách đa siêu phẳng kết hợp trọng số cụm: chiến lược "lớp-đối-cụm" và chiến lược "cụm-đối-lớp".

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

Cơ sở lý thuyết của luận án được xây dựng trên nền tảng giải tích lồi, tối ưu hóa toán học và lý thuyết học máy thống kê:

  • Hàm toàn phương và bài toán quy hoạch toàn phương (QP): Dạng chuẩn $Q(x) = \frac{1}{2} x^T G x + g^T x + \alpha$, trong đó $G$ là ma trận vuông đối xứng nửa xác định dương đảm bảo tính lồi của bài toán tối ưu.
  • Hệ điều kiện Karush-Kuhn-Tucker (KKT): Cung cấp điều kiện cần và đủ cho nghiệm tối ưu của bài toán quy hoạch toàn phương lồi có ràng buộc tuyến tính.
  • Bài toán đối ngẫu Lagrange: Chuyển đổi bài toán gốc với số chiều biến số lớn sang bài toán đối ngẫu có cấu trúc thuận lợi hơn cho việc tính toán.
  • Phương pháp bình phương tối thiểu: Thay thế ràng buộc bất đẳng thức bằng đẳng thức, sử dụng chuẩn bình phương của biến lơi để triệt tiêu ràng buộc dấu, dẫn đến việc giải hệ phương trình tuyến tính (SLEs).
  • Công thức Sherman-Morrison-Woodbury (SMW): Sử dụng để tính toán nghịch đảo của ma trận có dạng $(A + UV^T)^{-1}$, giúp giảm bậc của ma trận cần nghịch đảo từ kích thước số lượng mẫu xuống kích thước số chiều không gian đặc trưng.
  • Biến đổi không gian bằng kỹ thuật Kernel: Ánh xạ dữ liệu từ không gian gốc $R^n$ sang không gian đặc trưng nhiều chiều $H$ (hoặc không gian con $S = \text{span}(\Phi(C^T))$) thông qua hàm nhân $K(x^T, C^T) = \Phi(x^T)\Phi(C^T)$ thỏa mãn định lý Mercer để giải quyết bài toán phân lớp phi tuyến.
  • Ma trận hiệp phương sai cấu trúc: Cấu trúc lớp $\Sigma_A, \Sigma_B$ và cấu trúc cụm $\Sigma_{Ai}, \Sigma_{Bj}$ được xác định bằng công thức $\Sigma_X = \frac{1}{m_X} \sum_{x_j \in X} (x_j - \mu_X)(x_j - \mu_X)^T$, phục vụ định hướng hình học cho các mặt phân lớp.

Phương pháp nghiên cứu thực tế bao gồm:

  1. Phương pháp phân cụm dữ liệu: Sử dụng kỹ thuật phân cụm liên kết của Ward (Ward's hierarchical agglomerative clustering). Luận án loại trừ phương pháp k-means (do giới hạn ở cụm hình cầu và đòi hỏi kích thước cụm tương đương) và k-nearest neighbors (do chỉ dựa vào cục bộ lân cận, không thể hiện cấu trúc phân phối toàn cục).
  2. Chiến lược lớp-đối-cụm (Class-versus-cluster): Giả sử lớp dương có $k$ cụm và lớp âm có $l$ cụm, phương pháp xây dựng $(l + k)$ siêu phẳng, trong đó mỗi siêu phẳng nằm gần toàn bộ một lớp và cách xa một cụm cụ thể của lớp đối diện.
  3. Chiến lược cụm-đối-lớp (Cluster-versus-class): Xây dựng $(k + l)$ siêu phẳng, trong đó mỗi siêu phẳng nằm gần một cụm cụ thể của một lớp và cách xa toàn bộ lớp đối diện, kết hợp gán trọng số theo số lượng điểm dữ liệu của từng cụm.
  4. Phương pháp thực nghiệm: Cài đặt toàn bộ thuật toán đề xuất và các thuật toán đối sánh bằng ngôn ngữ lập trình Python. Kiểm thử độ chính xác phân loại và thời gian huấn luyện thông qua kỹ thuật đánh giá chéo (Cross-Validation) trên dữ liệu giả 2 chiều và các tập dữ liệu thực tế từ UCI. Mã nguồn thực nghiệm được công bố trên nền tảng GitHub.

Nguồn dữ liệu: Luận án sử dụng các tập dữ liệu mô phỏng giả lập 2 chiều (phục vụ trực quan hóa hình học) và tập hợp các bộ dữ liệu chuẩn nhị phân từ kho UCI Machine Learning Repository, được phân chia thành nhóm dữ liệu nhỏ và nhóm dữ liệu lớn.

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

Chương 1. Cơ sở toán học của SVM

Chương 1 hệ thống hóa cơ sở toán học chặt chẽ của bài toán tối ưu và thuật toán SVM tiêu chuẩn:

  • Trình bày dạng chuẩn của hàm toàn phương $Q(x)$, tính gradient $\nabla Q(x) = Gx + g$, ma trận Hessian $\nabla^2 Q(x) = G$, và tính chất lồi khi $G$ nửa xác định dương.
  • Định nghĩa bài toán quy hoạch toàn phương tổng quát dạng ma trận và phát biểu Định lý 1 về điều kiện KKT đối với điểm tối ưu $x^$ cùng các nhân tử Lagrange $\lambda^, \mu^*$.
  • Thiết lập quy trình đưa bài toán QP lồi về bài toán đối ngẫu Lagrange: từ hàm mục tiêu $L(x, \lambda, \mu)$, giải phương trình dừng $\nabla_x L = 0$ để biểu diễn biến gốc $x = G^{-1}(A^T \lambda + C^T \mu - g)$ và thu được bài toán đối ngẫu dạng toàn phương đối với $\lambda \ge 0$.
  • Phân tích bài toán phân lớp nhị phân cho tập dữ liệu $C \subset R^{m \times n}$ gồm lớp $A$ ($m_A$ điểm, nhãn $+1$) và lớp $B$ ($m_B$ điểm, nhãn $-1$). Thiết lập siêu phẳng phân lớp tuyến tính $S_{(w,b)} = {x \in R^n \mid w^T x + b = 0}$ và chuẩn hóa mặt quyết định chính tắc $\min_{i} |w^T x_i + b| = 1$. Khoảng cách lề được chứng minh bằng công thức $\rho(w, b) = 1/|w|$, dẫn đến bài toán cực tiểu hóa $\frac{1}{2}|w|^2$.
  • Trình bày bài toán siêu phẳng lề mềm cho dữ liệu chồng lấn: đưa vào các biến lơi $\xi_i \ge 0$ cùng hệ số phạt $c > 0$ trong hàm mục tiêu $\min \frac{1}{2}|w|^2 + c \sum_{i=1}^m \xi_i$ dưới ràng buộc $y_i(w^T x_i + b) \ge 1 - \xi_i$. Áp dụng hệ KKT và đối ngẫu Lagrange để rút ra nghiệm biểu diễn véc-tơ pháp tuyến qua các véc-tơ tựa $w = \sum_{i=1}^m \bar{\lambda}_i y_i x_i$.
  • Mở rộng phân lớp phi tuyến thông qua ánh xạ nâng chiều $\Phi(x)$ từ $R^n$ sang $R^m$, thiết lập ma trận Gram $D$ với các phần tử $D_{ij} = y_i y_j \Phi(x_i)^T \Phi(x_j)$ mà không cần tính trực tiếp trong không gian cao chiều.
  • Xây dựng bài toán phân lớp có trọng số cho trường hợp bất cân xứng về chi phí sai lầm, đưa vào hai trọng số phạt khác nhau $\delta^+$ và $\delta^-$ cho hai lớp $A$ và $B$.

Chương 2. Các biến thể của SVM

Chương 2 phân tích cơ chế toán học và hạn chế của các biến thể SVM tiêu biểu sử dụng hai siêu phẳng:

  • SVM xấp xỉ (PSVM): Giải bài toán quy hoạch toàn phương lồi chặt với ràng buộc đẳng thức $D(Cw + eb) + \xi = e$, hàm mục tiêu $\min \frac{c}{2}|\xi|^2 + \frac{1}{2}(|w|^2 + b^2)$. Nghiệm của nhân tử Lagrange được giải trực tiếp qua công thức $\lambda = (\frac{1}{c}I + H H^T)^{-1}e$ và áp dụng công thức Sherman-Morrison-Woodbury để nghịch đảo ma trận kích thước nhỏ.
  • GEPSVM: Tìm hai siêu phẳng không song song $f_+(x) = w_+^T x + b_+ = 0$ và $f_-(x) = w_-^T x + b_- = 0$ thông qua cực tiểu hóa thương Rayleigh, đưa về giải bài toán trị riêng suy rộng $Gz = \lambda Hz$. Nghiệm tương ứng với véc-tơ riêng của trị riêng nhỏ nhất.
  • SVM song sinh (TSVM): Thiết lập hai bài toán quy hoạch toàn phương lồi riêng biệt. Mỗi bài toán chỉ chứa ràng buộc của một lớp dữ liệu: $$\min \frac{1}{2} |Aw_+ + e_A b_+|^2 + c_+ e_B^T \xi \quad \text{với} \quad -(Bw_+ + e_B b_+) + \xi \ge e_B, \xi \ge 0$$ Bài toán đối ngẫu giải trên không gian biến $m_B$ và $m_A$, giúp giảm độ phức tạp từ $O(m^3)$ của SVM xuống $O(2(m/2)^3) = O(m^3/4)$, tức nhanh hơn khoảng 4 lần. Phân tích trường hợp phi tuyến dùng ma trận kernel $K(A, C^T)$ và $K(B, C^T)$.
  • TSVM dùng bình phương tối thiểu (LSTSVM): Thay thế toàn bộ ràng buộc bất đẳng thức trong TSVM bằng ràng buộc đẳng thức và sử dụng số hạng lỗi bậc hai $\frac{1}{2}c_+ \xi^T \xi$. Nghiệm của véc-tơ tham số siêu phẳng được tính trực tiếp từ hai hệ phương trình tuyến tính: $$z_+ = - \left[\frac{1}{c_+} H^T H + G^T G\right]^{-1} G^T e_B$$ loại bỏ hoàn toàn bước giải quy hoạch toàn phương đối ngẫu lặp.
  • S-TSVM: Tích hợp thông tin phân cụm dữ liệu theo thuật toán Ward. Đưa số hạng chính quy hóa cấu trúc cụm $\frac{1}{2} \lambda_+ w_+^T \Sigma_+ w_+$ vào hàm mục tiêu với $\Sigma_+ = \sum_{i=1}^k \Sigma_i^+$, ép siêu phẳng đi dọc theo phân bố hình học của các cụm trong lớp.

Chương 3. Phương pháp lớp đối cụm

Chương 3 trình bày đóng góp mới đầu tiên của luận án: chiến lược lớp-đối-cụm nhằm giải quyết sự phân mảnh cụm của lớp đối diện:

  • Đề xuất mô hình SVM có cấu trúc có trọng số (WS-SVM - Weighted Structural Support Vector Machine):
    • Thay vì chỉ tìm 2 siêu phẳng, thuật toán xác định $(l + k)$ siêu phẳng. Khi xét lớp dương đối với $l$ cụm của lớp âm, thuật toán giải $l$ bài toán quy hoạch toàn phương lồi. Mỗi bài toán tìm một siêu phẳng gần với toàn bộ lớp dương và cách xa cụm thứ $j$ của lớp âm ($B_j$).
    • Tích hợp trọng số kích thước mẫu và thông tin cấu trúc cụm vào hàm mục tiêu cho cả hai trường hợp tuyến tính và phi tuyến (sử dụng kernel).
    • Nghiệm của bài toán được dẫn xuất thông qua việc giải bài toán đối ngẫu Lagrange với kích thước ma trận giảm đi đáng kể.
  • Đề xuất mô hình Cải tiến của SVM dùng bình phương tối thiểu (ILS-SVM - Improvement Least Square Support Vector Machine):
    • Áp dụng kỹ thuật bình phương tối thiểu trên chiến lược lớp-đối-cụm. Chuyển đổi các bài toán tối ưu của WS-SVM sang bài toán có ràng buộc đẳng thức và sai số bình phương.
    • Nghiệm của mỗi siêu phẳng được tìm thông qua giải hệ phương trình tuyến tính, loại bỏ việc giải quy hoạch toàn phương, giảm mạnh thời gian huấn luyện.
  • Đánh giá thực nghiệm:
    • Thử nghiệm trên tập dữ liệu giả lập 2 chiều cho thấy các siêu phẳng của WS-SVM và ILS-SVM phân tách chính xác biên giữa các cụm phức tạp, không bị sai lệch như SVM tiêu chuẩn hay TSVM.
    • Thử nghiệm trên các tập dữ liệu chuẩn UCI:
      • Bảng 3.1 và 3.2 ghi nhận thời gian huấn luyện của WS-SVM với kernel tuyến tính và phi tuyến.
      • Bảng 3.3 và 3.4 so sánh độ chính xác của WS-SVM tuyến tính trên tập dữ liệu nhỏ và lớn của UCI.
      • Bảng 3.5 thể hiện kết quả phân lớp của WS-SVM phi tuyến.
      • Bảng 3.6 và 3.7 ghi nhận thời gian huấn luyện của ILS-SVM (kernel tuyến tính và phi tuyến).
      • Bảng 3.8, 3.9 và 3.10 đánh giá chi tiết độ chính xác và hiệu năng của ILS-SVM trên các tập dữ liệu nhỏ, lớn và phi tuyến của UCI đối sánh với các mô hình gốc.

Chương 4. Phương pháp cụm đối lớp

Chương 4 trình bày đóng góp mới thứ hai của luận án: chiến lược cụm-đối-lớp nhằm tận dụng tối đa đặc trưng phân bố cục bộ của từng cụm trong lớp:

  • Phân tích biến đổi của S-TSVM: Luận án chỉ ra điểm hạn chế khi S-TSVM gộp chung toàn bộ ma trận hiệp phương sai $\Sigma_+ = \sum \Sigma_i^+$ vào một bài toán duy nhất, làm triệt tiêu các đặc trưng phân bố dị hướng của từng cụm riêng biệt.
  • Đề xuất mô hình SVM dùng bình phương tối thiểu có trọng số (WLS-SVM - Weighted Least Square Support Vector Machine):
    • Xây dựng $(k + l)$ siêu phẳng phân lớp. Đối với cụm $A_i$ (gồm $m_{Ai}$ điểm) thuộc lớp dương, thuật toán xác định một siêu phẳng riêng biệt sao cho siêu phẳng này bám sát cấu trúc của riêng cụm $A_i$ và cách xa toàn bộ lớp âm $B$.
    • Đưa vào hàm mục tiêu ma trận hiệp phương sai riêng $\Sigma_{Ai}$ cùng trọng số tỷ lệ với số lượng phần tử $m_{Ai}$, phản ánh chính xác tỷ trọng đóng góp của cụm vào biên quyết định.
    • Thiết lập công thức giải bằng phương pháp bình phương tối thiểu cho cả trường hợp tuyến tính và trường hợp mở rộng phi tuyến bằng kernel, đưa việc tìm $(k + l)$ siêu phẳng về việc giải $(k + l)$ hệ phương trình đại số tuyến tính độc lập.
  • Đánh giá thực nghiệm:
    • Mô phỏng trên dữ liệu giả 2 chiều (Hình 4.1 và 4.2 thể hiện hành vi của S-TSVM; Hình 4.3 và 4.4 thể hiện WLS-SVM trên cấu trúc đơn giản và phức tạp) chứng minh WLS-SVM bao quát chính xác hình dạng từng cụm riêng biệt, giải quyết triệt để hiện tượng phân loại sai tại các vùng biên uốn lượn.
    • Kiểm chứng định lượng trên kho dữ liệu UCI:
      • Bảng 4.1 và 4.2 tổng kết thời gian huấn luyện của WLS-SVM với kernel tuyến tính và phi tuyến.
      • Bảng 4.3 và 4.4 báo cáo độ chính xác phân loại của WLS-SVM tuyến tính trên nhóm dữ liệu nhỏ và dữ liệu lớn UCI.
      • Bảng 4.5 ghi nhận hiệu năng phân loại của WLS-SVM phi tuyến, khẳng định sự cải thiện về thời gian xử lý nhờ kỹ thuật bình phương tối thiểu kết hợp độ chính xác cao đối với dữ liệu đa cụm.

Dưới đây là bảng tổng hợp so sánh đặc tính kỹ thuật giữa các thuật toán nền tảng và các thuật toán đề xuất trong luận án:

Thuật toán Chiến lược siêu phẳng Cơ sở toán học giải bài toán Khai thác cấu trúc cụm Trọng số kích thước cụm Dạng bài toán giải
SVM (Vapnik, 1995) 1 siêu phẳng duy nhất Nhân tử Lagrange / KKT Không Không 1 bài toán QP lớn
PSVM (Mangasarian, 2001) 2 siêu phẳng song song Đẳng thức / SMW Không Không 1 hệ phương trình tuyến tính
GEPSVM (Mangasarian, 2006) 2 siêu phẳng không song song Thương Rayleigh / Trị riêng Không Không 2 bài toán trị riêng suy rộng
TSVM (Jayadeva, 2007) 2 siêu phẳng không song song Nhân tử Lagrange / KKT Không Không 2 bài toán QP đối ngẫu nhỏ
LSTSVM (Kumar, 2009) 2 siêu phẳng không song song Bình phương tối thiểu Không Không 2 hệ phương trình tuyến tính
S-TSVM (Qi, 2013) 2 siêu phẳng không song song Nhân tử Lagrange / KKT Tổng hiệp phương sai $\Sigma$ Không 2 bài toán QP đối ngẫu
WS-SVM (Luận án đề xuất) $(l + k)$ siêu phẳng (lớp-đối-cụm) Nhân tử Lagrange / KKT Từng cụm riêng biệt Có tích hợp trọng số $(l + k)$ bài toán QP nhỏ
ILS-SVM (Luận án đề xuất) $(l + k)$ siêu phẳng (lớp-đối-cụm) Bình phương tối thiểu Từng cụm riêng biệt Có tích hợp trọng số $(l + k)$ hệ phương trình tuyến tính
WLS-SVM (Luận án đề xuất) $(k + l)$ siêu phẳng (cụm-đối-lớp) Bình phương tối thiểu Ma trận hiệp phương sai cụm Trọng số theo cỡ cụm $m_{Ai}, m_{Bj}$ $(k + l)$ hệ phương trình tuyến tính

Kết quả và những đóng góp mới

Luận án đã đạt được các kết quả nghiên cứu và đóng góp mới cụ thể về mặt lý luận khoa học cũng như thực tiễn ứng dụng như sau:

Về mặt khoa học:

  1. Đề xuất nhóm thuật toán phân lớp nhị phân cho dữ liệu có cấu trúc phức tạp theo chiến lược lớp-đối-cụm: Xây dựng thành công thuật toán WS-SVM (sử dụng phương pháp đối ngẫu Lagrange) và ILS-SVM (sử dụng phương pháp bình phương tối thiểu). Việc chia tách bài toán tối ưu thành $(l + k)$ bài toán con giúp thay thế bài toán quy hoạch toàn phương kích thước lớn bằng các bài toán quy hoạch toàn phương quy mô nhỏ hơn hoặc các hệ phương trình đại số tuyến tính, giảm đáng kể chi phí tính toán.
  2. Đề xuất nhóm thuật toán phân lớp nhị phân theo chiến lược cụm-đối-lớp: Cải tiến hạn chế của S-TSVM và đề xuất thuật toán WLS-SVM. Thuật toán đã kết hợp đồng thời việc khai thác thông tin cấu trúc hình học của từng cụm (qua ma trận hiệp phương sai riêng) và thông tin về số lượng điểm dữ liệu của mỗi cụm trong các lớp. Mô hình giải $(k + l)$ hệ phương trình tuyến tính độc lập thông qua phương pháp bình phương tối thiểu, cho phép tìm nghiệm toàn cục nhanh chóng.
  3. Mở rộng trọn vẹn cả hai chiến lược lớp-đối-cụm và cụm-đối-lớp sang trường hợp phân lớp phi tuyến thông qua hàm nhân kernel, giữ vững tính nhất quán toán học từ không gian mẫu sang không gian đặc trưng nhiều chiều.

Về mặt thực tiễn:

  1. Cung cấp giải pháp hiệu quả cho các bài toán phân lớp dữ liệu trong thế giới thực có cấu trúc phân bố không thuần nhất hoặc dữ liệu có độ mất cân bằng cao giữa các lớp (ví dụ một lớp chiếm 90% dữ liệu, lớp còn lại chỉ chiếm 10%).
  2. Đóng góp bộ mã nguồn hoàn chỉnh được lập trình bằng Python, lưu trữ và chia sẻ công khai trên nền tảng GitHub kèm theo các đường dẫn chi tiết trong phần phụ lục, tạo điều kiện thuận lợi cho việc kiểm chứng, tái lập kết quả và tích hợp vào các hệ thống phân loại mẫu thực tế.
  3. Kết quả nghiên cứu đã được công bố trong 5 công trình khoa học chuyên ngành, bao gồm 01 bài đăng trong chuyên san hội thảo quốc gia, 01 bài trong kỷ yếu hội thảo quốc tế, 01 bài trên Tạp chí Khoa học và Công nghệ (Đại học Khoa học, Đại học Huế), 01 bài trên Tạp chí Kỹ thuật và Công nghệ (Đại học Huế) và 01 bài trên Tạp chí Tin học và Điều khiển học.

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

Hạn chế của luận án:

  • Phạm vi nghiên cứu trong luận án tập trung chủ yếu vào bài toán phân loại nhị phân (hai lớp dữ liệu).
  • Hiệu năng của các thuật toán đề xuất (WS-SVM, ILS-SVM, WLS-SVM) phụ thuộc vào chất lượng của bước phân cụm sơ bộ dữ liệu bằng thuật toán liên kết của Ward; việc xác định số lượng cụm tối ưu ($k$ và $l$) trong từng lớp đòi hỏi quá trình tiền xử lý bổ sung.
  • Trong trường hợp dữ liệu có kích thước cực lớn, việc tính toán ma trận nghịch đảo cỡ $(m+1)$ trong không gian phi tuyến vẫn đòi hỏi chi phí bộ nhớ nhất định, cần áp dụng thêm công thức giảm chiều Sherman-Morrison-Woodbury hoặc kỹ thuật giả nghịch đảo.

Hướng nghiên cứu tiếp:

  • Mở rộng các chiến lược lớp-đối-cụm và cụm-đối-lớp cho bài toán phân loại đa lớp (multi-class classification).
  • Nghiên cứu cơ chế tự động xác định số lượng cụm tối ưu hoặc tích hợp các phương pháp phân cụm thích nghi trực tiếp vào quá trình tối ưu hóa siêu phẳng phân lớp.
  • Tiếp tục tối ưu hóa thuật toán tính toán ma trận nghịch đảo để nâng cao hơn nữa khả năng xử lý đối với các tập dữ liệu có quy mô dữ liệu lớn (big data).

Giá trị tham khảo

Luận án là tài liệu tham khảo có giá trị chuyên môn đối với:

  • Nghiên cứu sinh, học viên cao học và sinh viên các ngành Khoa học máy tính, Công nghệ thông tin và Toán ứng dụng đang thực hiện các đề tài nghiên cứu về học máy, khai phá dữ liệu và nhận dạng mẫu.
  • Các nhà nghiên cứu và kỹ sư dữ liệu quan tâm đến việc cải thiện hiệu năng phân lớp trên các tập dữ liệu mất cân bằng, dữ liệu đa phân bố hoặc dữ liệu có nhiễu cao.
  • Giảng viên giảng dạy các học phần chuyên sâu về Tối ưu hóa trong học máy, Lý thuyết máy học và Phương pháp véc-tơ hỗ trợ.

Các nội dung có giá trị tham khảo chuyên sâu nhất bao gồm:

  • Toàn bộ Chương 1 với hệ thống dẫn dắt toán học chặt chẽ từ bài toán quy hoạch toàn phương lồi, hệ điều kiện KKT đến bài toán đối ngẫu Lagrange của SVM.
  • Các công thức nghiệm giải tích dạng đóng cho các siêu phẳng trong phương pháp bình phương tối thiểu ở Chương 3 và Chương 4.
  • Phụ lục mã nguồn Python và hướng dẫn kết nối các bộ dữ liệu thực nghiệm chuẩn từ kho UCI.

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

1. Tại sao luận án lại chọn thuật toán phân cụm liên kết của Ward mà không dùng k-means hay k-nearest neighbors?

Theo phân tích của tác giả ở Chương 2, thuật toán k-means có nhược điểm lớn là chỉ phù hợp với các cụm có dạng hình cầu và giả định số lượng phần tử trong mỗi cụm phải xấp xỉ nhau, do đó không phản ánh đúng dữ liệu có cấu trúc phức tạp trong thực tế. Trong khi đó, thuật toán k-nearest neighbors chỉ phân loại dựa trên $k$ điểm láng giềng gần nhất mang tính cục bộ, không hỗ trợ trích xuất ma trận hiệp phương sai để mô tả hình học toàn thể của cụm. Thuật toán liên kết của Ward cho phép gom cụm dựa trên việc tối thiểu hóa phương sai gia tăng, trích xuất chính xác cấu trúc cụm thông qua ma trận hiệp phương sai $\Sigma_{Ai}, \Sigma_{Bj}$.

2. Sự khác biệt cốt lõi giữa hai chiến lược "lớp-đối-cụm" và "cụm-đối-lớp" là gì?

  • Chiến lược "lớp-đối-cụm" (Chương 3) tìm kiếm $(l + k)$ siêu phẳng, trong đó mỗi siêu phẳng được tối ưu sao cho nằm gần toàn bộ một lớp dữ liệu và đẩy ra xa một cụm duy nhất của lớp đối diện. Chiến lược này giải quyết bài toán khi một lớp bị phân mảnh bởi nhiều cụm của lớp kia.
  • Chiến lược "cụm-đối-lớp" (Chương 4) tìm kiếm $(k + l)$ siêu phẳng, trong đó mỗi siêu phẳng bám sát riêng một cụm của một lớp và cách xa toàn bộ lớp đối diện. Chiến lược này đi kèm việc gán trọng số kích thước mẫu cho từng cụm riêng biệt, giúp phản ánh cấu trúc phân bố dị hướng của từng cụm tốt hơn.

3. Phương pháp bình phương tối thiểu trong ILS-SVM và WLS-SVM mang lại ưu thế gì so với việc giải bài toán đối ngẫu Lagrange trong WS-SVM?

Việc sử dụng phương pháp đối ngẫu Lagrange đòi hỏi phải giải các bài toán quy hoạch toàn phương có ràng buộc bất đẳng thức thông qua các thuật toán lặp số học, chiếm nhiều thời gian tính toán. Ngược lại, kỹ thuật bình phương tối thiểu chuyển toàn bộ ràng buộc bất đẳng thức thành ràng buộc đẳng thức và sử dụng chuẩn sai số bậc hai, cho phép đạo hàm trực tiếp hàm mục tiêu và đưa về việc giải hệ phương trình tuyến tính (SLEs) thông qua phép tính nghịch đảo ma trận. Điều này giúp rút ngắn đáng kể thời gian huấn luyện mô hình.

4. Thuật toán TSVM đạt được tốc độ nhanh hơn SVM tiêu chuẩn xấp xỉ bao nhiêu lần và vì sao?

Trong Chương 2, tác giả chứng minh rằng SVM tiêu chuẩn giải một bài toán quy hoạch toàn phương cỡ $m$ biến với độ phức tạp tính toán xấp xỉ $O(m^3)$. Trong khi đó, TSVM chia nhỏ thành hai bài toán quy hoạch toàn phương cỡ $m_A$ và $m_B$. Giả sử số lượng điểm trong hai lớp bằng nhau ($m_A \approx m_B \approx m/2$), độ phức tạp của TSVM là $O(2 \times (m/2)^3) = O(m^3/4)$. Do đó, thời gian huấn luyện của TSVM nhanh hơn xấp xỉ 4 lần so với SVM tiêu chuẩn.

5. Luận án giải quyết vấn đề kích thước ma trận lớn khi tính nghịch đảo trong trường hợp phi tuyến như thế nào?

Khi mở rộng sang trường hợp phi tuyến sử dụng ma trận kernel, kích thước ma trận cần tính nghịch đảo tăng lên cấp $(m + 1)$. Để giảm thiểu chi phí tính toán khi số lượng mẫu dữ liệu lớn, luận án sử dụng công thức giảm chiều ma trận nghịch đảo Sherman-Morrison-Woodbury (SMW): $$(A + UV^T)^{-1} = A^{-1} - A^{-1} U (I + V^T A^{-1} U)^{-1} V^T A^{-1}$$ Công thức này cho phép chuyển đổi phép nghịch đảo ma trận từ kích thước dữ liệu lớn xuống kích thước không gian chiều đặc trưng nhỏ hơn. Ngoài ra, kỹ thuật tính toán giả nghịch đảo cũng được áp dụng khi lập trình thuật toán thực tế.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Thế Cường đã giải quyết trọn vẹn bài toán nâng cao hiệu năng phân lớp dữ liệu nhị phân có cấu trúc phức tạp bằng cách tiếp cận toán học tối ưu và có hệ thống. Bằng việc đề xuất hai chiến lược "lớp-đối-cụm" (mô hình WS-SVM, ILS-SVM) và "cụm-đối-lớp" (mô hình WLS-SVM), công trình đã khai thác thành công thông tin hình học ma trận hiệp phương sai và trọng số kích thước mẫu của từng cụm dữ liệu. Các kết quả thực nghiệm trên tập dữ liệu mô phỏng 2 chiều và các bộ dữ liệu chuẩn UCI khẳng định tính đúng đắn, tốc độ huấn luyện vượt trội và khả năng ứng dụng thực tế của các phương pháp đề xuất.