Tổng quan luận án

Luận án tiến sĩ với đề tài "Phương pháp lựa chọn thuộc tính và kỹ thuật gom cụm dữ liệu phân loại sử dụng tập thô" do nghiên cứu sinh Đỗ Sĩ Trường thực hiện dưới sự hướng dẫn khoa học của PGS.TS Nguyễn Thanh Tùng, thuộc chuyên ngành Khoa học máy tính (Mã số ngành: 9480101) tại Trường Đại học Lạc Hồng, bảo vệ năm 2023.

Trong tiến trình khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Databases – KDD), quá trình xử lý chuẩn bao gồm 5 công đoạn: Lựa chọn dữ liệu, Tiền xử lý dữ liệu, Rút gọn dữ liệu, Khai phá dữ liệu và Đánh giá/diễn giải tri thức. Trong đó, công đoạn khai phá dữ liệu giữ vai trò trọng tâm với hai kỹ thuật nền tảng là phân lớp dữ liệu (học có giám sát) và gom cụm dữ liệu (học không có giám sát). Cùng với sự phát triển của công nghệ thu thập dữ liệu, các tập dữ liệu trong thực tế (như dữ liệu gen, phân loại văn bản, truy xuất hình ảnh) thường có kích thước rất lớn với số lượng thuộc tính (chiều dữ liệu) khổng lồ. Điều này làm cho các thuật toán khai phá và học máy truyền thống bị giảm tốc độ xử lý và không thể hoạt động hiệu quả. Do đó, việc rút gọn dữ liệu trước khi khai phá nhằm giảm chiều không gian nhưng vẫn bảo toàn thông tin cốt lõi là một yêu cầu cấp thiết. Rút gọn dữ liệu có thể thực hiện thông qua biến đổi thuộc tính (như PCA, ICA) hoặc lựa chọn thuộc tính (attribute selection/reduction).

Bên cạnh đó, trong nhiều ứng dụng thực tiễn, dữ liệu thường xuất hiện dưới dạng dữ liệu phân loại/phạm trù (categorical data) – loại dữ liệu có miền giá trị hữu hạn, không có thứ tự và chỉ cho phép so sánh bằng hoặc khác nhau ($a = b$ hoặc $a \neq b$). Do không thể xác định hàm khoảng cách tự nhiên (như metric Euclide hay Mahalanobis), các kỹ thuật gom cụm thông thường trên không gian số không thể áp dụng trực tiếp cho dữ liệu phân loại. Lý thuyết tập thô (Rough Sets Theory – LTTT) do Zdzislaw Pawlak đề xuất năm 1982 là công cụ toán học xử lý hiệu quả tính mơ hồ, không chắc chắn mà không đòi hỏi thông tin phụ trợ (như phân phối xác suất trong thống kê hay độ thuộc trong tập mờ). Tuy nhiên, việc ứng dụng lý thuyết tập thô vào hai bài toán lựa chọn thuộc tính và gom cụm dữ liệu phân loại vẫn còn tồn tại những khoảng trống nghiên cứu rõ rệt:

  1. Đối với bài toán lựa chọn thuộc tính: Nhiều thuật toán hiện nay có thể loại bỏ các thuộc tính không liên quan nhưng không thể loại bỏ hiệu quả các thuộc tính dư thừa. Thuộc tính dư thừa làm tăng độ phức tạp tính toán và ảnh hưởng xấu đến độ chính xác phân lớp của các mô hình học máy.
  2. Đối với bài toán gom cụm dữ liệu phân loại: Các thuật toán gom cụm dữ liệu phân loại dựa trên tập thô hiện có thường có độ chính xác thấp, độ phức tạp tính toán cao, khó khăn trong việc tìm ra thuộc tính gom cụm tối ưu và chưa xử lý tốt tính không chắc chắn tại ranh giới giữa các cụm.

Từ các vấn đề trên, luận án xác định hai mục tiêu nghiên cứu cụ thể:

  • Mục tiêu thứ nhất: Nghiên cứu phương pháp lựa chọn thuộc tính có thể loại bỏ hiệu quả đồng thời các thuộc tính không liên quan và cả các thuộc tính dư thừa.
  • Mục tiêu thứ hai: Cải tiến các thuật toán gom cụm dữ liệu phân loại, đặc biệt là bài toán lựa chọn thuộc tính nhằm cho kết quả gom cụm tốt hơn các thuật toán cơ bản hiện có.

Đối tượng nghiên cứu: Các hệ thông tin, bảng quyết định có thể chứa dữ liệu mơ hồ, không chắc chắn.

Phạm vi nghiên cứu: Các phương pháp khai phá dữ liệu theo hướng tiếp cận lý thuyết tập thô, tập trung vào bài toán tìm tập rút gọn (lựa chọn thuộc tính) trong bảng quyết định và bài toán gom cụm trên các tập dữ liệu phân loại.

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

Tổng quan các nghiên cứu trước được tác giả hệ thống hóa qua hai nhánh chính: các công trình ứng dụng lý thuyết tập thô trong nước và các thuật toán lựa chọn thuộc tính, gom cụm dữ liệu phân loại trên thế giới.

Về nghiên cứu trong nước, tác giả điểm lại các luận án tiến sĩ tiêu biểu về rút gọn thuộc tính trong bảng quyết định:

  • Hoàng Thị Lan Giao (2014): Đề xuất các thuật toán heuristic tìm tập rút gọn và tập rút gọn xấp xỉ của bảng quyết định nhất quán sử dụng các phép toán trong đại số quan hệ và ma trận phân biệt.
  • Nguyễn Đức Thuần (2015): Đề xuất thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ nhất quán dựa vào phủ tập thô.
  • Nguyễn Long Giang (2016): Nghiên cứu phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ sử dụng metric.

Về nghiên cứu quốc tế, tác giả phân tích các hướng tiếp cận kinh điển và hiện đại:

  • Phương pháp ma trận phân biệt (Skowron, 1992): Sử dụng ma trận phân biệt và hàm phân biệt Bool để tìm tất cả các tập rút gọn và tập lõi ($Core$). Phương pháp này có độ phức tạp bài toán thuộc lớp NP-khó, chỉ áp dụng được trên các bảng dữ liệu có kích thước nhỏ.
  • Phương pháp dựa trên độ phụ thuộc Pawlak: Tiêu biểu là thuật toán QuickReduct (Jensen & Shen / Chouchoulas & Shen, 2001) áp dụng chiến lược tìm kiếm bổ sung dần (forward generation) dựa vào mức tăng độ phụ thuộc $\gamma_B(d)$.
  • Phương pháp dựa trên độ phụ thuộc tương đối: Thuật toán RelativeReduct do Han và các cộng sự đề xuất, sử dụng phép chiếu trong đại số quan hệ $\Pi_B(U)$ và chiến lược loại bỏ dần (backward generation) với độ phức tạp tính toán $O(k n \log n)$.
  • Phương pháp dựa trên Entropy thông tin: Thuật toán CEBARKNC do Wang và cộng sự đề xuất, xác định tập rút gọn dựa trên Shannon entropy có điều kiện $H(D|C)$ với độ phức tạp $O(|C|^2 |U| + |C| |U|^3)$.
  • Các phương pháp gom cụm dữ liệu phân loại sử dụng tập thô: Các thuật toán gom cụm thuộc tính và đối tượng như TR (Total Roughness), MDA (Maximum degree of Dependency of Attributes), MMR (Min-Min-Roughness), MGR (Mean Gain Ratio) và MNF.

Khoảng trống luận án lựa chọn giải quyết: Hầu hết các thuật toán heuristic hiện có hoặc chỉ loại bỏ thuộc tính không liên quan (mà bỏ sót việc lọc thuộc tính dư thừa), hoặc chỉ tiếp cận theo một hàm mục tiêu đơn lẻ. Luận án giải quyết khoảng trống này bằng cách kết hợp lý thuyết tập thô với các độ đo entropy trong lý thuyết thông tin (cụ thể là Biến thể thông tin chuẩn hóa - NVI) và kỹ thuật gom cụm medoids (PAM) để tạo ra thuật toán rút gọn thuộc tính ACBRC. Đồng thời, đối với bài toán gom cụm dữ liệu phân loại, luận án khắc phục hạn chế về việc chọn thuộc tính phân cụm và độ không chắc chắn của MMR và MGR bằng thuật toán phân cấp phân đôi dần MMNVI.

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

1. Cơ sở lý thuyết và khung phân tích

Luận án xây dựng trên nền tảng toán học của Lý thuyết tập thô kết hợp với Lý thuyết thông tin:

  • Lý thuyết tập thô (Pawlak):

    • Hệ thông tin: Bộ đôi $IS = (U, A)$, với $U$ là tập hữu hạn đối tượng, $A$ là tập hữu hạn thuộc tính, mỗi thuộc tính $a \in A$ là ánh xạ $a: U \rightarrow V_a$.
    • Quan hệ không phân biệt được: Với $B \subseteq A$, quan hệ $IND(B) = {(u, v) \in U^2 : a(u) = a(v), \forall a \in B}$. Quan hệ này chia $U$ thành các lớp tương đương $[u]_B$, tạo thành phân hoạch $U/B$.
    • Các phép xấp xỉ tập hợp: Cho $X \subseteq U$, $B$-xấp xỉ dưới $\underline{B}X = \bigcup { [x]_B : [x]_B \subseteq X }$ và $B$-xấp xỉ trên $\overline{B}X = \bigcup { [x]_B : [x]_B \cap X \neq \emptyset }$. Vùng $B$-biên $BN_B(X) = \overline{B}X - \underline{B}X$.
    • Độ chính xác và độ thô: Độ chính xác xấp xỉ $\alpha_B(X) = \frac{|\underline{B}X|}{|\overline{B}X|}$; Độ thô của tập hợp $R_B(X) = 1 - \alpha_B(X)$.
    • Bảng quyết định và Miền dương: Bảng quyết định $DT = (U, C \cup {d})$ với $C$ là tập thuộc tính điều kiện, $d$ là thuộc tính quyết định. Miền dương của $d$ đối với $B \subseteq C$ là $POS_B(d) = \bigcup_{X \in U/d} \underline{B}X$.
    • Độ phụ thuộc: $\gamma_B(d) = \frac{|POS_B(d)|}{|U|}$. Tập rút gọn $Red(C)$ là tập con tối tiểu $B \subseteq C$ sao cho $\gamma_B(d) = \gamma_C(d)$. Tập lõi $Core(C) = \bigcap Red(C)$.

  • Lý thuyết thông tin liên quan:

    • Phân phối xác suất của thuộc tính: $P(a = x_i) = P(x_i) = \frac{|X_i|}{|U|}$.
    • Shannon Entropy: $H(a) = -\sum_{i=1}^m P(x_i) \log_2 P(x_i)$.
    • Entropy đồng thời: $H(a, b) = -\sum_{i=1}^m \sum_{j=1}^n P(a = x_i, b = y_j) \log_2 P(a = x_i, b = y_j)$.
    • Entropy có điều kiện: $H(a|b) = -\sum_{j=1}^n P(b = y_j) \sum_{i=1}^m P(a = x_i | b = y_j) \log_2 P(a = x_i | b = y_j)$.
    • Thông tin tương hỗ: $I(a; b) = H(a) - H(a|b) = H(b) - H(b|a)$.
    • Biến thể thông tin chuẩn hóa (Normalized Variation of Information - NVI): $$NVI(a, b) = 1 - \frac{I(a; b)}{H(a, b)} = \frac{H(a|b) + H(b|a)}{H(a, b)}$$ Luận án chứng minh $NVI(a, b)$ là một metric khoảng cách chuẩn tắc trên không gian thuộc tính, thỏa mãn tính chất đối xứng, không âm, giá trị nằm trong đoạn $[0, 1]$ và thỏa mãn bất đẳng thức tam giác: $NVI(a, b) \le NVI(a, c) + NVI(c, b)$.
+-------------------------------------------------------------------------------+
|                    KHUNG LÝ THUYẾT VÀ PHÂN TÍCH CỦA LUẬN ÁN                   |
+---------------------------------------+---------------------------------------+
|          LÝ THUYẾT TẬP THÔ            |          LÝ THUYẾT THÔNG TIN          |
| - Quan hệ không phân biệt IND(B)      | - Shannon Entropy H(a)                |
| - Lớp tương đương [u]_B               | - Entropy đồng thời H(a, b)           |
| - Xấp xỉ trên, xấp xỉ dưới            | - Entropy có điều kiện H(a|b)         |
| - Miền dương POS_B(d), Độ phụ thuộc   | - Thông tin tương hỗ I(a; b)          |
| - Bảng quyết định, Tập rút gọn, Lõi   | - Metric Biến thể TT chuẩn hóa (NVI)  |
+---------------------------------------+---------------------------------------+
                                    |
                                    v
+-------------------------------------------------------------------------------+
|                     HAI THUẬT TOÁN ĐÓNG GÓP CỦA TÁC GIẢ                       |
|                                                                               |
|  1. Thuật toán ACBRC (Rút gọn thuộc tính):                                    |
|     Lọc thuộc tính -> Gom cụm thuộc tính (PAM + NVI) -> Chọn đại diện         |
|                                                                               |
|  2. Thuật toán MMNVI (Gom cụm dữ liệu phân loại):                             |
|     Lọc đơn trị -> Chọn phân cụm (min MNVI) -> Tách cụm (min sum Entropy)     |
+-------------------------------------------------------------------------------+

2. Phương pháp nghiên cứu và nguồn dữ liệu thực nghiệm

  • Phương pháp thực hiện: Phương pháp nghiên cứu thuật toán và thực nghiệm định lượng. Luận án tiến hành tổng hợp lý thuyết, thiết kế mô hình giải thuật, phân tích độ phức tạp thời gian/không gian, sau đó cài đặt chương trình và chạy thử nghiệm đối sánh.
  • Nguồn dữ liệu: Sử dụng các bộ dữ liệu thực tế và chuẩn quốc tế lấy từ kho dữ liệu máy học UCI (UCI Machine Learning Repository).
  • Công cụ và phương pháp đánh giá:
    • Đối với rút gọn thuộc tính: Sử dụng thuật toán quy nạp cây quyết định C5.0 và mô hình phân lớp Naïve Bayes để kiểm chứng độ chính xác phân lớp trước và sau khi rút gọn, so sánh số lượng thuộc tính được chọn và thời gian thực thi (giây).
    • Đối với gom cụm dữ liệu phân loại: Đánh giá kết quả trên 8 tập dữ liệu UCI chuẩn bằng 3 chỉ số kiểm định: Độ thuần khiết tổng thể (Overall Purity - OP), Chỉ số ngẫu nhiên hiệu chỉnh (Adjusted Rand Index - ARI), và Thông tin tương hỗ chuẩn hóa (Normalized Mutual Information - NMI).

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

CHƯƠNG 1. KHÁI QUÁT VỀ LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG TRONG KHAI PHÁ DỮ LIỆU

Chương 1 hệ thống hóa các định nghĩa toán học cơ bản của lý thuyết tập thô (Hệ thông tin, quan hệ không phân biệt, phép xấp xỉ trên/dưới, độ thô, độ chính xác, bảng quyết định, miền dương, độ phụ thuộc Pawlak, tập rút gọn và tập lõi) và các độ đo trong lý thuyết thông tin (Shannon entropy, entropy có điều kiện, thông tin tương hỗ, metric NVI).

Tác giả trình bày cấu trúc 4 thuật toán cơ sở của lý thuyết tập thô:

  1. Thuật toán 1.1: Xác định lớp tương đương
  2. Thuật toán 1.2: Xác định xấp xỉ dưới
  3. Thuật toán 1.3: Xác định xấp xỉ trên
  4. Thuật toán 1.4: Xác định miền dương

Các thuật toán cơ sở này đều đạt độ phức tạp thời gian là $O(k n \log n)$ và độ phức tạp không gian là $O(n)$, trong đó $n = |U|$ là số đối tượng và $k = |A|$ là số thuộc tính.

Thuật toán cơ sở Đầu vào Đầu ra Độ phức tạp thời gian Độ phức tạp không gian
Xác định lớp tương đương Tập $U$, tập thuộc tính $B$ Tập các lớp tương đương $L$ ($U/IND(B)$) $O(k n \log n)$ $O(n)$
Xác định xấp xỉ dưới Tập $U$, tập $B$, tập đối tượng $X$ Tập $\underline{B}X$ $O(k n \log n)$ $O(n)$
Xác định xấp xỉ trên Tập $U$, tập $B$, tập đối tượng $X$ Tập $\overline{B}X$ $O(k n \log n)$ $O(n)$
Xác định miền dương Hệ $S=(U, A, V, f), A=C \cup D$ Tập $POS_C(D)$ $O(k n \log n)$ $O(n)$

Chương này cũng phân tích chi tiết ứng dụng của tập thô trong các công đoạn KDD (tiền xử lý dữ liệu: xử lý giá trị thiếu, rời rạc hóa dữ liệu, rút gọn dữ liệu; khai phá dữ liệu: phân lớp, gom cụm, phát hiện luật kết hợp), đồng thời chỉ ra 4 hạn chế của lý thuyết tập thô kinh điển:

  • Dữ liệu khai phá bắt buộc phải ở dạng rời rạc;
  • Dữ liệu phải đầy đủ, không bị nhiễu;
  • Tri thức trích xuất nhạy cảm với sự biến động dữ liệu;
  • Các thuật toán kinh điển thường có độ phức tạp tính toán cao.

CHƯƠNG 2. LỰA CHỌN THUỘC TÍNH SỬ DỤNG LÝ THUYẾT TẬP THÔ

Chương 2 tập trung phân tích bài toán lựa chọn thuộc tính. Sau khi phân biệt hai nhóm phương pháp tiếp cận lọc (Filter) và bao bọc (Wrapper), các chiến lược tìm kiếm tập con (bổ sung dần - Forward và loại bỏ dần - Backward), tác giả điểm luận chi tiết các thuật toán rút gọn thuộc tính hiện có:

  • Phương pháp ma trận phân biệt (Skowron): Thiết lập ma trận đối xứng $M(DT) = (m_{ij})$, xây dựng hàm phân biệt $f_{DT}$, đưa về dạng tuyển chuẩn tắc (DNF) để trích xuất tập rút gọn và tập lõi.
  • Phương pháp độ phụ thuộc QuickReduct: Bổ sung dần từng thuộc tính có $SIG(a, B, d) = \gamma_{B \cup {a}}(d) - \gamma_B(d)$ lớn nhất cho đến khi $\gamma_R(d) = \gamma_C(d)$.
  • Phương pháp độ phụ thuộc tương đối RelativeReduct: Dựa trên tỷ số $k_B(d) = \frac{card(U/IND(B))}{card(U/IND(B \cup {d}))}$, loại bỏ dần thuộc tính nếu sau khi bỏ mà $k_{R-{c}}(d) = 1$ với độ phức tạp $O(k n \log n)$.
  • Phương pháp entropy thông tin CEBARKNC: Tìm tập rút gọn dựa trên entropy có điều kiện $H(D|R) = H(D|C)$ với độ phức tạp $O(|C|^2|U| + |C||U|^3)$.

Đề xuất thuật toán ACBRC (Attribute Clustering Based Reduct Computing): Thuật toán ACBRC được xây dựng nhằm giải quyết đồng thời việc loại bỏ thuộc tính không liên quan và thuộc tính dư thừa. Thuật toán vận hành qua 3 công đoạn chính:

  1. Công đoạn 1 (Lọc không liên quan): Loại bỏ các thuộc tính không có liên quan hoặc có mức tương quan không đáng kể đối với thuộc tính quyết định.
  2. Công đoạn 2 (Gom cụm thuộc tính): Gom cụm các thuộc tính liên quan còn lại thành $k$ cụm thích hợp bằng giải thuật Phân hoạch xung quanh Medoids (Partitioning Around Medoids - PAM / k-medoids) với hàm khoảng cách là metric Biến thể thông tin chuẩn hóa $NVI(a, b)$.
  3. Công đoạn 3 (Chọn đại diện cụm): Trong mỗi cụm thu được, chọn ra duy nhất một thuộc tính đại diện có độ liên quan lớn nhất với thuộc tính quyết định $d$. Hợp của các thuộc tính đại diện này tạo thành tập rút gọn xấp xỉ.

Kết quả thực nghiệm ACBRC: Luận án thực hiện kiểm thử trên các tập dữ liệu benchmark UCI, so sánh với các thuật toán rút gọn khác. Kết quả thể hiện qua các bảng dữ liệu về thời gian thực hiện, số thuộc tính rút gọn và độ chính xác phân lớp bằng hai bộ phân lớp C5.0 và Naïve Bayes, khẳng định ACBRC tạo ra tập rút gọn kích thước nhỏ nhưng vẫn duy trì độ chính xác phân lớp tương đương hoặc cao hơn.

CHƯƠNG 3. GOM CỤM DỮ LIỆU SỬ DỤNG LÝ THUYẾT TẬP THÔ

Chương 3 khảo sát bài toán gom cụm dữ liệu phân loại không giám sát. Tác giả phân tích các thuật toán gom cụm dựa trên tập thô đã công bố:

  • Thuật toán TR (Total Roughness): Lựa chọn thuộc tính dựa trên tổng độ thô $TR(a_i)$ với mọi thuộc tính còn lại.
  • Thuật toán MDA (Maximum degree of Dependency of Attributes): Dựa trên độ phụ thuộc lớn nhất của các thuộc tính.
  • Thuật toán MMR (Min-Min-Roughness / Min-Min-Mean-Roughness): Chọn thuộc tính dựa trên cực tiểu hóa độ thô trung bình.
  • Thuật toán MGR (Mean Gain Ratio): Sử dụng tỷ lệ lợi thông tin trung bình.

Đề xuất thuật toán MMNVI (Minimum Mean Normalized Variation of Information): Thuật toán MMNVI là phương pháp gom cụm phân cấp theo cơ chế phân đôi dần (divisive hierarchical clustering). Tại mỗi bước lặp, MMNVI thực hiện 3 thao tác:

  • Bước 1: Loại bỏ tất cả các thuộc tính chỉ nhận duy nhất một giá trị trên tập dữ liệu đang xét.
  • Bước 2: Tính toán giá trị biến thể thông tin chuẩn hóa trung bình $MNVI(a_i)$ của từng thuộc tính đối với tất cả các thuộc tính còn lại: $$MNVI(a_i) = \frac{1}{|A|-1} \sum_{a_j \in A, j \neq i} NVI(a_i, a_j)$$ Chọn thuộc tính phân cụm $a^$ là thuộc tính có giá trị $MNVI$ nhỏ nhất: $a^ = \arg\min_{a_i \in A} MNVI(a_i)$.
  • Bước 3: Phân chia tập dữ liệu thành các lớp tương đương sinh bởi $a^*$. Chọn lớp tương đương có tổng entropy của các thuộc tính là nhỏ nhất để tạo thành một cụm độc lập; hợp của tất cả các lớp tương đương còn lại được giữ lại làm tập dữ liệu để tiếp tục phân chia ở bước lặp sau.

Quá trình phân đôi lặp lại cho đến khi đạt được số lượng cụm mong muốn định trước.

Kết quả thực nghiệm MMNVI: Luận án tiến hành thử nghiệm trên 8 bộ dữ liệu chuẩn UCI gồm:

  1. Soybean Small
  2. Breast Cancer Wisconsin
  3. Car Evaluation
  4. Vote
  5. Chess
  6. Mushroom
  7. Balance Scale
  8. Zoo

Hiệu năng của MMNVI được so sánh trực tiếp với hai thuật toán MMR và MGR thông qua 3 thước đo: Độ thuần khiết tổng thể (Overall Purity - OP), Chỉ số ngẫu nhiên hiệu chỉnh (Adjusted Rand Index - ARI) và Thông tin tương hỗ chuẩn hóa (Normalized Mutual Information - NMI). Kết quả thực nghiệm cho thấy MMNVI đạt chất lượng gom cụm tốt hơn hoặc tương đương với MMR và MGR trên hầu hết các tập dữ liệu kiểm định.

CHƯƠNG 4. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

Chương 4 tổng kết toàn bộ các kết quả đạt được về mặt lý thuyết và thực nghiệm, đồng thời vạch ra các định hướng mở rộng nghiên cứu trong tương lai.

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

Luận án đã đạt được các đóng góp khoa học chính sau:

1. Đóng góp về mặt lý luận và giải thuật

  • Chứng minh toán học metric NVI: Chứng minh hoàn chỉnh tính chất metric của Biến thể thông tin chuẩn hóa ($NVI$) trong không gian thuộc tính thỏa mãn bất đẳng thức tam giác thông qua bất đẳng thức entropy có điều kiện $H(a|b) \le H(a|c) + H(c|b)$.
  • Đề xuất thuật toán rút gọn thuộc tính ACBRC: Thiết kế thành công quy trình 3 giai đoạn kết hợp gom cụm medoids (PAM) và metric NVI để tính toán tập rút gọn xấp xỉ trong bảng quyết định. Giải thuật có khả năng loại bỏ đồng thời cả thuộc tính không liên quan và thuộc tính dư thừa, đồng thời xét đến các thuộc tính tương tác kết hợp.
  • Đề xuất thuật toán gom cụm dữ liệu phân loại MMNVI: Xây dựng thuật toán gom cụm phân cấp phân đôi dần sử dụng tiêu chuẩn chọn thuộc tính phân cụm dựa trên $MNVI$ cực tiểu và tách cụm dựa trên cực tiểu hóa tổng entropy của các lớp tương đương. Giải thuật xử lý hiệu quả tính không chắc chắn trong dữ liệu phân loại mà không cần giả định trước về hàm khoảng cách hình học.

2. Đóng góp về mặt thực tiễn và công bố

  • Cài đặt và thực nghiệm toàn diện trên 8 tập dữ liệu chuẩn quốc tế từ kho dữ liệu UCI (Soybean Small, Breast Cancer Wisconsin, Car Evaluation, Vote, Chess, Mushroom, Balance Scale, Zoo), chứng minh tính hiệu quả của ACBRC qua các mô hình C5.0, Bayes và của MMNVI qua 3 chỉ số OP, ARI, NMI khi so sánh với MMR và MGR.
  • Công bố khoa học:
    • 02 bài báo khoa học trên tạp chí chuyên ngành trong nước: Journal of Computer Science and Cybernetics (năm 2022 và năm 2023).
    • 01 bài báo khoa học quốc tế.
    • 03 báo cáo tại các hội thảo khoa học quốc gia.

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

Dựa trên các nội dung văn bản luận án trình bày, các hạn chế nội tại và hướng phát triển được xác định như sau:

1. Hạn chế

  • Các thuật toán đề xuất chủ yếu tập trung xử lý dữ liệu ở dạng phân loại/phạm trù (hoặc dữ liệu liên tục đã qua giai đoạn rời rạc hóa trước).
  • Phương pháp lý thuyết tập thô kinh điển còn nhạy cảm với dữ liệu có độ nhiễu cao hoặc tập dữ liệu có giá trị bị thiếu.
  • Trong thuật toán ACBRC, hiệu quả tính toán tập rút gọn xấp xỉ còn phụ thuộc vào việc lựa chọn số cụm $k$ thích hợp trong giai đoạn phân chia thuộc tính.

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

  • Mở rộng và phát triển các thuật toán rút gọn thuộc tính và gom cụm dữ liệu cho các hệ thông tin phức tạp hơn, bao gồm hệ thông tin không đầy đủ (chứa dữ liệu thiếu) và hệ thông tin dữ liệu hỗn hợp (chứa đồng thời cả thuộc tính số liên tục và thuộc tính phân loại).
  • Nghiên cứu các phương pháp tự động xác định số cụm tối ưu trong thuật toán ACBRC nhằm tối ưu hóa kích thước tập rút gọn mà không cần chỉ định tham số thủ công.
  • Ứng dụng các thuật toán đã đề xuất vào các bài toán khai phá dữ liệu thực tế có số chiều lớn trong y sinh học, phân loại văn bản và hệ thống hỗ trợ quyết định.

Giá trị tham khảo

Luận án mang lại giá trị tham khảo khoa học và ứng dụng thực tiễn rõ nét cho các nhóm đối tượng:

  • Nghiên cứu sinh, học viên cao học và nhà nghiên cứu ngành Khoa học máy tính, Trí tuệ nhân tạo, Khai phá dữ liệu:

    • Cung cấp tài liệu tham khảo có cấu trúc chặt chẽ về cách kết hợp Lý thuyết tập thô với Lý thuyết thông tin (Shannon entropy, Mutual Information, NVI).
    • Cung cấp phép chứng minh toán học chi tiết về tính chất metric của NVI trong không gian thuộc tính.
    • Cung cấp mã giả, phân tích độ phức tạp và quy trình thực nghiệm của các thuật toán kinh điển (QuickReduct, RelativeReduct, CEBARKNC, TR, MDA, MMR, MGR) cũng như các thuật toán mới (ACBRC, MMNVI).

  • Giảng viên và người xây dựng chương trình đào tạo sau đại học:

    • Có thể sử dụng làm tài liệu giảng dạy chuyên đề về Tiền xử lý dữ liệu, Giảm chiều dữ liệu (Feature Selection) và Học không giám sát trên dữ liệu phi số (Categorical Data Clustering).

  • Kỹ sư dữ liệu và chuyên viên phát triển hệ thống phân tích thông minh:

    • Tham khảo giải thuật ACBRC để tích hợp vào các bước tiền xử lý lọc đặc trưng cho các bài toán phân lớp dữ liệu quy mô lớn, giúp tối ưu hóa thời gian huấn luyện mô hình.
    • Sử dụng giải thuật MMNVI để phân đoạn đối tượng trong các cơ sở dữ liệu khách hàng, phân loại bệnh phẩm hoặc phân tích mẫu dữ liệu mà các thuộc tính hoàn toàn là dạng phân loại.

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

1. Vì sao không thể áp dụng trực tiếp các hàm khoảng cách hình học thông thường (như khoảng cách Euclide) cho dữ liệu phân loại?

Dữ liệu phân loại (categorical data) có miền giá trị hữu hạn và không có thứ tự tự nhiên (ví dụ: quốc tịch, màu tóc). Trong miền giá trị này, chỉ có thể thực hiện so sánh bằng hoặc khác nhau ($a = b$ hoặc $a \neq b$) chứ không có ý nghĩa về độ lớn hay khoảng cách độ dài đại số. Do đó, việc áp dụng các metric khoảng cách hình học như Euclide hay Mahalanobis là không phù hợp, đòi hỏi phải sử dụng các công cụ xử lý thông tin không chắc chắn như lý thuyết tập thô hoặc các độ đo biến thể thông tin từ lý thuyết thông tin.

2. Cơ chế loại bỏ đồng thời thuộc tính không liên quan và thuộc tính dư thừa của thuật toán ACBRC diễn ra như thế nào?

ACBRC thực hiện việc này qua quy trình 3 công đoạn:

  • Công đoạn 1: Loại bỏ trực tiếp các thuộc tính không có liên quan đến thuộc tính quyết định $d$.
  • Công đoạn 2: Gom các thuộc tính liên quan còn lại thành các cụm tương đồng bằng thuật toán PAM dựa trên metric Biến thể thông tin chuẩn hóa ($NVI$). Các thuộc tính trong cùng một cụm sẽ có mức độ chia sẻ thông tin cao (tương đồng lớn với nhau).
  • Công đoạn 3: Chỉ chọn duy nhất một thuộc tính có độ phụ thuộc lớn nhất với thuộc tính quyết định từ mỗi cụm để đưa vào tập rút gọn. Việc chỉ lấy một đại diện cho mỗi cụm giúp loại bỏ các thuộc tính dư thừa còn lại trong cụm đó, đồng thời việc lấy đại diện của tất cả các cụm giúp giữ lại đầy đủ các thông tin cốt lõi cần thiết cho phân lớp.

3. Biến thể thông tin chuẩn hóa (NVI) được tính toán như thế nào và có vai trò gì trong luận án?

Biến thể thông tin chuẩn hóa giữa hai thuộc tính $a$ và $b$ được xác định theo công thức: $$NVI(a, b) = 1 - \frac{I(a; b)}{H(a, b)} = \frac{H(a|b) + H(b|a)}{H(a, b)}$$ Trong đó $I(a; b)$ là thông tin tương hỗ, $H(a, b)$ là entropy đồng thời, và $H(a|b)$ là entropy có điều kiện. Luận án đã chứng minh $NVI$ là một metric chuẩn tắc có giá trị trong đoạn $[0, 1]$ và thỏa mãn bất đẳng thức tam giác. NVI đóng vai trò là hàm khoảng cách phổ quát giữa các thuộc tính trong thuật toán gom cụm thuộc tính ACBRC và là đại lượng nền tảng để tính chỉ số $MNVI$ lựa chọn thuộc tính phân cụm trong thuật toán MMNVI.

4. Thuật toán gom cụm MMNVI thực hiện việc phân đôi dữ liệu tại mỗi bước lặp dựa trên nguyên tắc nào?

Tại mỗi bước lặp, MMNVI thực hiện:

  1. Loại bỏ các thuộc tính đơn trị (chỉ nhận một giá trị duy nhất).
  2. Tính $MNVI(a_i) = \frac{1}{|A|-1} \sum_{a_j \in A, j \neq i} NVI(a_i, a_j)$ và chọn thuộc tính phân cụm $a^*$ có giá trị $MNVI$ nhỏ nhất.
  3. Sinh các lớp tương đương của tập dữ liệu hiện tại theo thuộc tính $a^*$. Chọn lớp tương đương có tổng entropy của các thuộc tính nhỏ nhất để tách thành một cụm kết quả; hợp của các lớp tương đương còn lại sẽ là tập dữ liệu đầu vào cho bước lặp phân đôi tiếp theo.

5. Hiệu năng của thuật toán gom cụm MMNVI được kiểm chứng trên những bộ dữ liệu nào và sử dụng các chỉ số đánh giá nào?

Thuật toán MMNVI được kiểm chứng thực nghiệm trên 8 bộ dữ liệu chuẩn quốc tế từ kho UCI gồm: Soybean Small, Breast Cancer Wisconsin, Car Evaluation, Vote, Chess, Mushroom, Balance Scale, Zoo. Hiệu năng gom cụm được so sánh đối chuẩn với hai thuật toán MMR và MGR thông qua 3 chỉ số đánh giá: Độ thuần khiết tổng thể (Overall Purity - OP), Chỉ số ngẫu nhiên hiệu chỉnh (Adjusted Rand Index - ARI) và Thông tin tương hỗ chuẩn hóa (Normalized Mutual Information - NMI).

Kết luận

Luận án tiến sĩ của nghiên cứu sinh Đỗ Sĩ Trường đã giải quyết hai bài toán quan trọng trong khai phá dữ liệu gồm lựa chọn thuộc tính và gom cụm dữ liệu phân loại dựa trên sự kết hợp giữa Lý thuyết tập thô và Lý thuyết thông tin. Tác giả đã đề xuất hai giải thuật mới: thuật toán ACBRC cho phép loại bỏ đồng thời các thuộc tính không liên quan và dư thừa trong bảng quyết định thông qua kỹ thuật gom cụm medoids với metric $NVI$; và thuật toán phân cấp MMNVI giúp tối ưu hóa việc lựa chọn thuộc tính phân cụm và phân đôi dữ liệu phân loại. Các kết quả thực nghiệm trên 8 tập dữ liệu chuẩn UCI cùng các bài báo khoa học đã công bố khẳng định tính đúng đắn về lý thuyết và hiệu quả thực tiễn của các phương pháp được đề xuất trong luận án.