Tổng quan luận án

Luận án tiến sĩ kỹ thuật với đề tài "Nghiên cứu, phát triển một số phương pháp khai phá dữ liệu trên dữ liệu có cấu trúc" được thực hiện bởi nghiên cứu sinh Hoàng Minh Quang, dưới sự hướng dẫn khoa học của GS. Vũ Đức Thi và GS. Nguyễn Ngọc San tại Học viện Công nghệ Bưu chính Viễn thông (Bộ Thông tin và Truyền thông), hoàn thành năm 2020 thuộc chuyên ngành Hệ thống thông tin (mã số: 09.04).

Khai phá dữ liệu lớn là lĩnh vực công nghệ có tiềm năng ứng dụng rộng rãi trong các ngành như y tế, giao thông, tài chính, giáo dục nhằm hỗ trợ ra quyết định, cắt giảm chi phí và phát triển sản phẩm, dịch vụ. Tuy nhiên, lĩnh vực này đối mặt với thách thức lớn xuất phát từ hai đặc trưng cơ bản: tính lớn (volume) và tính đa dạng, phức tạp (variety/complexity). Dữ liệu có dung lượng lớn đòi hỏi lưu trữ phân tán, dẫn đến thời gian truy xuất thông tin cao; đồng thời độ phức tạp tính toán của nhiều thuật toán khai phá mẫu là hàm mũ hoặc không đa thức. Mặt khác, dữ liệu được thu thập từ nhiều nguồn dị biệt (hệ quản trị cơ sở dữ liệu, mạng internet, mạng xã hội, truyền hình kỹ thuật số, thiết bị di động, thiết bị IoT) tạo ra các định dạng khác nhau (có cấu trúc, bán cấu trúc, phi cấu trúc). Dù ở định dạng nào, dữ liệu đều có thể quy về hai dạng biểu diễn có cấu trúc cốt lõi là dữ liệu dạng bảng (bảng quyết định) và dữ liệu dạng đồ thị (cơ sở dữ liệu đồ thị). Từ đó, khoảng trống nghiên cứu chính mà luận án tập trung giải quyết là:

  1. Nhu cầu trích xuất thông tin cốt lõi, loại bỏ dữ liệu dư thừa để tăng giá trị của dữ liệu được khai phá.
  2. Tối ưu hóa tính toán, cải thiện tốc độ và chi phí xử lý nhằm đưa các bài toán có độ phức tạp thời gian không đa thức về thời gian đa thức dưới các điều kiện ràng buộc nhất định.

Mục tiêu nghiên cứu của luận án được xác định cụ thể cho hai dạng dữ liệu:

  1. Đối với dữ liệu dạng bảng: Nghiên cứu các bài toán giảm dư thừa dữ liệu, tìm một rút gọn thuộc tính không dùng tiếp cận heuristic trong thời gian đa thức, tìm rút gọn đối tượng nhằm thu nhỏ kích thước bảng mà vẫn bảo toàn việc tìm kiếm tất cả các rút gọn thuộc tính, và cải tiến tốc độ sinh cây quyết định so với thuật toán ID3.
  2. Đối với dữ liệu dạng đồ thị: Tối ưu hóa tính toán bài toán khai phá đồ thị con thường xuyên đóng bằng cách giải quyết bài toán kiểm tra đẳng cấu đồ thị con trong thời gian đa thức dưới ràng buộc dữ liệu chuẩn hóa; giải quyết bài toán phân loại đa nhãn cho đồ thị khi dữ liệu đồ thị không có biểu diễn véctơ.

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

  • Đối tượng nghiên cứu: Dữ liệu có cấu trúc dạng bảng quyết định nhất quán trong hệ thống thông tin và dữ liệu biểu diễn dạng đồ thị của cơ sở dữ liệu đồ thị giao tác (như cấu trúc hóa học, sinh học, mạng máy tính, mạng xã hội).
  • Phạm vi nghiên cứu: Tập trung vào bảng quyết định nhất quán với ba bài toán: loại bỏ thuộc tính dư thừa/tìm một rút gọn thuộc tính không heuristic, tìm rút gọn đối tượng, sinh cây quyết định; và cơ sở dữ liệu giao tác đồ thị với hai bài toán: khai phá đồ thị con thường xuyên đóng (closed frequent subgraph) và phân loại đồ thị đa nhãn (multi-label graph classification).

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

Tổng quan tài liệu trong luận án điểm lại các hướng nghiên cứu chính về xử lý và khai phá dữ liệu lớn trên thế giới:

  • Đánh chỉ mục và truy vấn dữ liệu: Yan et al. (2004, 2005) [90], [91].
  • Tìm kiếm theo từ khóa: Ding et al. (2014) [18], Kacholia et al. (2005) [54].
  • So khớp đồ thị: Cheng et al. (2014) [15], (2015) [16].
  • Mô tả và tóm lược đồ thị lớn: Aggarwal et al. (2010) [2], Hassan & Zaki (2006) [38], Sun et al. (2012) [77].
  • Khai phá mẫu thường xuyên: Agrawal & Srikant (1994) [3], Borgelt & Berthold (2002) [7], Chi et al. (2005) [14], Deshpande et al. (2005) [24], Huan et al. (2003, 2004) [39], [40], Inokuchi et al. (2000, 2003) [41], [43], Kuramochi & Karypis (2001, 2004, 2005) [49], [51], [52], Nijssen & Kok (2004, 2005) [61], [62], Yan & Han (2002, 2003) [94], [95].
  • Phân cụm dữ liệu: Aggarwal & Wang (2010) [1], Biemann (2006) [5], Brandes et al. (2003) [8], Deshpande et al. (2005) [24], Ester et al. (1996) [27].
  • Phân lớp và phân loại dữ liệu: Ben-Hur et al. (2008) [10], Deshpande et al. (2005) [23], [24], Gärtner et al. (2003) [33], [34], Kashima et al. (2003) [50], Ralaivola et al. (2005) [70], Saigo et al. (2004) [71], Tsuda (2010) [82], Tsuda et al. (2002) [83], Vapnik (1998) [85], Yao & Zhao (2008) [97], Yao et al. (2008) [98], [99].
  • Khai phá dữ liệu phát triển theo thời gian: Aggarwal (2003) [4], Borgelt & Berthold (2002) [7], Bifet & Gavaldà (2009) [6], Chen et al. (2003) [9], Hulten et al. (2001) [53].

Về hướng tiếp cận lý thuyết tập thô trên dữ liệu bảng:

  • Zdzislaw Pawlak (1982, 1991) [64], [67] đề xuất lý thuyết tập thô, định nghĩa quan hệ bất khả phân biệt, bảng quyết định, phép xấp xỉ trên, xấp xỉ dưới, miền dương và rút gọn thuộc tính.
  • Các công trình phát triển phương pháp rút gọn thuộc tính: Miao & Wang (1999) [59], Susmaga (1998) [75], Kryszkiewicz (1998) [48], Skowron & Rauszer (1992) [73], Zhong et al. (2001) [100], Pagliani (1997) [60], Inuiguchi et al. (2003) [42], Wang et al. (2002) [92], Du & Hu (2004) [22].
  • Susmaga (1998) [75] đã chứng minh tìm rút gọn thuộc tính tối thiểu và phụ thuộc tối thiểu là bài toán NP-hard. Kryszkiewicz (1998) [48] chỉ ra thuật toán tìm tất cả các rút gọn thuộc tính dựa trên miền dương có độ phức tạp hàm mũ theo số thuộc tính. Do đó, phần lớn nghiên cứu trước đây chọn giải pháp heuristic để tìm một rút gọn thuộc tính.

Về hướng tiếp cận lý thuyết cơ sở dữ liệu quan hệ:

  • Demetrovics, Vũ Đức Thi, Nguyễn Ngọc San và cộng sự (1992, 1995, 1998, 2012, 2017) [20], [21], [78], [79], [80] nghiên cứu về phụ thuộc hàm, bao đóng, họ $f$, khóa, phản khóa, hệ Sperner, tập bằng nhau và hệ bằng nhau cực đại.

Về hướng tiếp cận khai phá đồ thị, phân tích khái niệm chính thức và lý thuyết Dempster-Shafer:

  • Ganter & Wille (1999) [30] phát triển lý thuyết Phân tích khái niệm chính thức (Formal Concept Analysis - FCA).
  • Shafer (1976) [74], Grabisch et al. (2009) [36], Davey & Priestley (2002) [32] phát triển cơ sở toán học về cấu trúc dàn giao, hàm khối, biến đổi và đồng biến đổi Möbius, hàm niềm tin và luật kết hợp Dempster.

Khoảng trống luận án lựa chọn giải quyết:

  1. Trên dữ liệu dạng bảng: Khắc phục việc phải dùng heuristic khi tìm một rút gọn thuộc tính, phát triển thuật toán tìm một rút gọn thuộc tính có độ phức tạp thời gian đa thức không dùng heuristic; xây dựng phương pháp rút gọn đối tượng (thu nhỏ chiều ngang) trong thời gian đa thức mà vẫn bảo toàn việc tìm kiếm toàn bộ tập rút gọn thuộc tính.
  2. Trên dữ liệu dạng đồ thị: Khắc phục độ phức tạp không đa thức của kiểm tra đẳng cấu đồ thị con trong khai phá đồ thị con thường xuyên đóng bằng thuật toán PSI-CFSM trong thời gian đa thức; thiết lập độ đo khoảng cách trực tiếp trên dàn giao khái niệm để phân loại đồ thị đa nhãn bằng lý thuyết Dempster-Shafer mà không cần chuyển đổi sang không gian véctơ.

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

Luận án sử dụng và tích hợp 7 cơ sở lý thuyết toán học và khoa học máy tính:

  1. Lý thuyết cơ sở dữ liệu quan hệ: Sử dụng các khái niệm quan hệ $R$, phụ thuộc hàm $A \to B$, họ đầy đủ phụ thuộc hàm $F_R$, họ $f$, lược đồ quan hệ $S = \langle \Omega, F \rangle$, bao đóng $A^+$, quan hệ Armstrong, khóa, khóa tối tiểu, hệ Sperner, tập các phản khóa $K^{-1}$, tập bằng nhau $E_R$, hệ bằng nhau cực đại $M_R$, họ các tập tối tiểu của thuộc tính $K_a^R, K_a^S$, họ các tập cực đại không là tập tối tiểu $(K_a^R)^{-1}, (K_a^S)^{-1}$.
  2. Lý thuyết tập thô (Rough Sets): Hệ thông tin $S = (U, A, V, f)$, bảng quyết định $DS = (U, C \cup {d}, V, f)$, bảng quyết định nhất quán ($C \to {d}$), quan hệ bất khả phân biệt $IND(P)$, phân hoạch $U/P$, lớp tương đương $[u]P$, xấp xỉ trên $\overline{B}X$, xấp xỉ dưới $\underline{B}X$, vùng biên $BN_B(X)$, miền dương $POS_B(D)$, rút gọn thuộc tính $RED(C)$, ma trận phân biệt $M = (m{ij})$ và tập lõi $CORE(C) = \bigcap RED(C) = {a \in C : (\exists i, j) m_{ij} = {a}}$.
  3. Lý thuyết đồ thị và khai phá đồ thị: Đồ thị gắn nhãn $G = (V, E, \Sigma_V, \Sigma_E, l)$, quan hệ đẳng cấu đồ thị con ($G \sqsubseteq G'$), cơ sở dữ liệu đồ thị $GD$, ngưỡng hỗ trợ tối thiểu $\sigma$, độ hỗ trợ $sup_G$, tập đồ thị con thường xuyên $FS$, tập đồ thị con thường xuyên đóng $CS$, ma trận kề $M$, mã ma trận kề $code(M)$, ma trận dạng chuẩn $CAM(G)$ (Canonical Adjacency Matrix) theo thứ tự từ điển chuẩn (standard lexicographic order).
  4. Tập có thứ tự và dàn giao (Lattices): Poset hữu hạn cục bộ $(X, \le)$, toán tử meet/infimum (glb), toán tử join/supremum (lub), hệ thống tập hợp, hệ đóng $\zeta$ và tập đóng.
  5. Phân tích khái niệm chính thức (FCA): Ngữ cảnh chính thức $(G, M, I)$, kết nối Galois $(A^I, B^I)$, khái niệm chính thức $(A, B)$ với phạm vi (extent) $A = B^I$ và ý định (intent) $B = A^I$, thứ tự khái niệm con - cha, dàn giao khái niệm $\mathcal{B}(G, M, I)$ và định lý cơ bản về dàn giao khái niệm.
  6. Biến đổi và đồng biến đổi Möbius: Hàm Möbius $\mu$, biến đổi Möbius $m(x) = \sum_{y \le x} \mu(y, x) f(y)$, đồng biến đổi Möbius $q(x) = \sum_{y \ge x} m(y)$ trên poset hữu hạn cục bộ.
  7. Lý thuyết Dempster-Shafer: Không gian phân biệt $\Omega$, hàm cấp phát khối $m: 2^\Omega \to [0, 1]$, phần tử tiêu điểm ($m(A) > 0$), hàm niềm tin $bel(A) = \sum_{B \subseteq A} m(B)$, hàm sự thật $pl(A) = \sum_{B \cap A \neq \emptyset} m(B) = 1 - bel(A^c)$, hàm tính chất chung $q(A) = \sum_{A \subseteq B} m(B)$, sức chứa liên hợp $\bar{v}(A) = 1 - v(A^c)$, luật kết hợp Dempster $m = m_1 \oplus m_2$ và $q(A) = q_1(A) q_2(A)$.

Phương pháp nghiên cứu kết hợp:

  • Phương pháp nghiên cứu lý thuyết/toán học hình thức: Thiết lập các định nghĩa, định lý, bổ đề; xây dựng các chứng minh toán học về tính đúng đắn, tính đầy đủ và tính dừng; phân tích độ phức tạp thuật toán theo ký hiệu $O$-lớn.
  • Phương pháp thiết kế thuật toán và cấu trúc dữ liệu: Xây dựng các giải thuật duyệt, tỉa nhánh, kiểm tra bất biến đại số, thao tác trên cây mã chuẩn hóa (CAM Tree, DFS Code Tree) và dàn giao khái niệm.
  • Phương pháp thực nghiệm kiểm chứng: Đánh giá thời gian chạy và hiệu năng thuật toán trên các bộ dữ liệu thực nghiệm chuẩn từ kho dữ liệu Machine Learning UCI (Balance scale, Kr-vs-kp, Breast cancer, Car, Tic-tac-toe) và kho dữ liệu NCI (Molecula, HIV AIDS, Chemical compound).

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

Chương 1: Kiến thức chuẩn bị

Chương 1 hệ thống hóa các định nghĩa, tính chất, bổ đề và định lý của 7 lĩnh vực lý thuyết nền tảng đã nêu. Điểm kết nối cốt lõi được tác giả xác lập tại chương này là sự tương đương toán học giữa cấu trúc cơ sở dữ liệu quan hệ và lý thuyết tập thô:

  • Xem tập đối tượng $U = {u_1, \dots, u_m}$ của bảng quyết định nhất quán $DS = (U, C \cup {d}, V, f)$ như một quan hệ trên tập thuộc tính $R = C \cup {d}$.
  • Hệ bằng nhau cực đại $M_d$ đối với thuộc tính quyết định $d$ được định nghĩa: $$M_d = {A \in E_U : d \notin A, \nexists B \in E_U : d \notin B, A \subsetneq B}$$
  • Mối liên hệ giữa tập tất cả các rút gọn thuộc tính của bảng quyết định nhất quán $RED(C)$ với họ các tập tối tiểu của thuộc tính $d$ trên quan hệ $U$: $RED(C) = K_d^U - {d}$.
  • Thiết lập định lý cơ bản về dàn giao khái niệm: dàn giao $\mathcal{B}(G, M, I)$ là dàn giao đầy đủ, đảm bảo mọi cặp phần tử đồ thị con thường xuyên đóng đều tồn tại phần tử infimum và supremum, làm cơ sở toán học để tính khoảng cách giữa các đồ thị.

Chương 2: Khai phá dữ liệu dạng bảng

Chương 2 trình bày các thuật toán đề xuất để khai phá dữ liệu trên bảng quyết định nhất quán:

  1. Loại bỏ thuộc tính dư thừa:

    • Định nghĩa tập các thuộc tính rút gọn $REAT(C) = \bigcup_{A \in RED(C)} A = (\bigcup_{A \in K_d^r} A) - {d}$. Thuộc tính dư thừa là thuộc tính không thuộc $REAT(C)$.
    • Thủ tục EqualitySet(DS) xác định tập bằng nhau $E_r$ với độ phức tạp không quá $|R| \cdot |U|^2$.
    • Thủ tục MaximalEqualityForD(Er) tìm hệ bằng nhau cực đại $M_d$ với độ phức tạp không quá $|E_r|^2$.
    • Thuật toán RemoveRedundantAttribute(DS) loại bỏ toàn bộ thuộc tính dư thừa với độ phức tạp thời gian tồi nhất là $O(|U|^4 + |C \cup {d}|)$ — đa thức theo số hàng và số cột.
    • Bổ đề 2.4 chứng minh $M_d = (K_d^r)^{-1}$, nghĩa là $M_d$ chính là họ các phản khóa của họ tập tối tiểu $K_d^r$.

  2. Rút gọn thuộc tính không dùng heuristic:

    • Thủ tục AntikeySet xây dựng tập phản khóa $K^{-1}$ từ hệ Sperner $K$ trong thời gian $O(|U|^2 \sum_{q=0}^{m-1} t_q u_q)$.
    • Thủ tục AMinimalKey và thuật toán MinimalKeySet(K) tìm tập khóa tối tiểu $H$ từ $K$ với độ phức tạp không quá $O(|U|^2 |K| |K^{-1}|^2)$ khi $l_q < l_m$.
    • Thuật toán AnAttributeReduct(DS) tìm một rút gọn thuộc tính $D \in RED(C)$ bằng cách duyệt loại dần các thuộc tính điều kiện dựa trên điều kiện bao hàm trong $M_d$. Độ phức tạp thời gian của AnAttributeReduct(DS) là $O(|C| \cdot |U|^4)$, hoàn toàn trong thời gian đa thức mà không sử dụng tiếp cận heuristic.

  3. Rút gọn đối tượng bảng quyết định nhất quán:

    • Đưa ra Định nghĩa 2.3 về rút gọn đối tượng: Bảng quyết định $DS' = (U', C \cup {d}, V, f)$ là một rút gọn đối tượng của $DS = (U, C \cup {d}, V, f)$ nếu $U' \subseteq U$, $RED_U(C) = RED_{U'}(C)$ và $\forall u \in U', RED_U(C) \neq RED_{U' - {u}}(C)$.
    • Thuật toán AnObjectReduct(DS) kiểm tra tuần tự từng đối tượng $u_{i+1}$, nếu loại bỏ $u_{i+1}$ mà hệ bằng nhau cực đại không đổi ($M_d^{T - {u_{i+1}}} = M_d^U$) thì đối tượng đó là dư thừa và bị loại khỏi bảng. Tác giả chứng minh Định lý 2.4 bằng quy nạp toán học dựa trên tính chất $M_d = (K_d^r)^{-1}$ và tính duy nhất của cặp hệ Sperner $(K, K^{-1})$. Thuật toán chạy trong thời gian đa thức.

  4. Sinh cây quyết định từ bảng rút gọn hai chiều (IDRT):

    • Kết hợp bảng đã rút gọn thuộc tính và rút gọn đối tượng cùng tập thuộc tính lõi $CORE(C)$ để sinh cây quyết định nhanh hơn thuật toán ID3 truyền thống.
Bảng minh họa các bước rút gọn (Dữ liệu chơi Golf) Số thuộc tính điều kiện Số đối tượng (hàng)
Bảng quyết định nhất quán gốc (Bảng 2.1) 6 thuộc tính 14 đối tượng
Bảng loại bỏ thuộc tính dư thừa (Bảng 2.2) 4 thuộc tính 14 đối tượng
Bảng rút gọn đối tượng (Bảng 2.3) 6 thuộc tính 6 đối tượng
Bảng rút gọn thuộc tính miền dương (Bảng 2.4) 3 thuộc tính 14 đối tượng
Bảng kết hợp rút gọn đối tượng và thuộc tính (Bảng 2.5) 3 thuộc tính 6 đối tượng
  1. Đánh giá thực nghiệm Chương 2: Thực nghiệm trên các bộ dữ liệu chuẩn UCI (Balance scale, Kr-vs-kp, Breast cancer, Car, Tic-tac-toe) xác nhận thuật toán IDRT trên bảng rút gọn cho tốc độ thực thi nhanh hơn thuật toán ID3 gốc (đơn vị đo: millisecond).
Bộ dữ liệu thực nghiệm UCI Kích thước mẫu / Thuộc tính Tốc độ thực hiện ID3 (ms) Tốc độ thực hiện IDRT (ms)
Balance scale 625 đối tượng / 4 thuộc tính Đã đánh giá trong Bảng 2.8 Nhanh hơn ID3
Kr-vs-kp 3196 đối tượng / 36 thuộc tính Đã đánh giá trong Bảng 2.8 Nhanh hơn ID3
Breast cancer 286 đối tượng / 9 thuộc tính Đã đánh giá trong Bảng 2.8 Nhanh hơn ID3
Car 1728 đối tượng / 6 thuộc tính Đã đánh giá trong Bảng 2.8 Nhanh hơn ID3
Tic-tac-toe 958 đối tượng / 9 thuộc tính Đã đánh giá trong Bảng 2.8 Nhanh hơn ID3

Chương 3: Khai phá dữ liệu đồ thị

Chương 3 giải quyết hai bài toán trên cơ sở dữ liệu đồ thị giao tác:

  1. Khai phá đồ thị con thường xuyên đóng và thuật toán PSI-CFSM:

    • Phân tích bài toán khai phá đồ thị con thường xuyên đóng ($CS$). Bài toán con cốt lõi là kiểm tra đẳng cấu đồ thị con ($G \sqsubseteq G'$), vốn là bài toán NP-complete trong trường hợp tổng quát.
    • Luận án đề xuất thuật toán PSI-CFSM (Pattern-growth based Subgraph Isomorphism for Closed Frequent Subgraph Mining) sử dụng ma trận kề dạng chuẩn $CAM(G)$, biểu diễn mã $code(M)$ theo thứ tự từ điển chuẩn kết hợp cây tìm kiếm DFS Code Tree và CAM Tree.
    • Tác giả chứng minh rằng dưới các ràng buộc về thứ tự tập nhãn đỉnh/cạnh và mô hình máy truy cập ngẫu nhiên, bài toán kiểm tra đẳng cấu đồ thị con trong quy trình khai phá đồ thị con thường xuyên đóng được giải quyết trong thời gian đa thức. Quy trình sinh ứng viên ($k$-subgraph) và tỉa các nhánh không thường xuyên hoặc không thỏa mãn dạng chuẩn (DFSC) được tối ưu hóa.

  2. Phân loại đồ thị đa nhãn sử dụng lý thuyết Dempster-Shafer trên dàn giao khái niệm:

    • Khi dữ liệu đồ thị không có biểu diễn véctơ trực tiếp, các phương pháp phân loại dựa trên khoảng cách hình học thông thường không áp dụng được.
    • Luận án đề xuất xây dựng dàn giao khái niệm $\mathcal{B}(G, M, I)$ từ ngữ cảnh chính thức giữa các đồ thị giao tác và tập tất cả các đồ thị con thường xuyên đóng.
    • Thiết lập độ đo tương tự/khoảng cách giữa hai đồ thị trên dàn giao khái niệm thông qua cấu trúc infimum ($\bigwedge$) và supremum ($\bigvee$) của các khái niệm chính thức tương ứng.
    • Áp dụng biến đổi Möbius và đồng biến đổi Möbius để xây dựng hàm cấp phát khối $m$, hàm niềm tin $bel$, hàm sự thật $pl$ và hàm tính chất chung $q$.
    • Sử dụng luật kết hợp Dempster ($m_1 \oplus m_2$, $q = q_1 \cdot q_2$) để kết hợp chứng cứ từ tập $k$ láng giềng gần nhất ($k$-NN) trên dàn giao, từ đó gán nhãn đa nhãn cho đồ thị mới.

  3. Đánh giá thực nghiệm Chương 3: Thực nghiệm trên các tập dữ liệu hợp chất hóa học và sinh học chuẩn NCI (như HIV AIDS, Chemical compound, Molecula) chứng minh thuật toán PSI-CFSM khai phá đồ thị con thường xuyên đóng với thời gian tính toán (đơn vị: giây) tối ưu hơn so với các phương pháp đối sánh, và thuật toán phân loại đa nhãn đạt độ chính xác phân loại tin cậy mà không cần véctơ hóa đồ thị.

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

Luận án tự nêu các đóng góp mới về mặt lý luận khoa học và thực tiễn kỹ thuật:

  1. Về lý luận và giải thuật khai phá dữ liệu dạng bảng:

    • Đề xuất phương pháp và thuật toán AnAttributeReduct tìm một rút gọn thuộc tính trên bảng quyết định nhất quán trong thời gian đa thức ($O(|C| \cdot |U|^4)$), không sử dụng tiếp cận heuristic như các nghiên cứu trước.
    • Đề xuất khái niệm và thuật toán AnObjectReduct tìm một rút gọn đối tượng của bảng quyết định nhất quán trong thời gian đa thức, chứng minh toán học rằng việc loại bỏ các đối tượng dư thừa hoàn toàn bảo toàn việc tìm kiếm tập tất cả các rút gọn thuộc tính ($RED_{U'}(C) = RED_U(C)$).
    • Cải tiến phương pháp sinh cây quyết định (IDRT) dựa trên bảng dữ liệu thu gọn cả hai chiều (thuộc tính và đối tượng) kết hợp tập lõi $CORE(C)$, chứng minh tốc độ thực thi nhanh hơn thuật toán ID3.

  2. Về lý luận và giải thuật khai phá dữ liệu dạng đồ thị:

    • Chứng minh bài toán đẳng cấu đồ thị con được giải quyết trong thời gian đa thức trong quy trình khai phá đồ thị con thường xuyên đóng (thuật toán PSI-CFSM) với các ràng buộc về thứ tự nhãn chuẩn hóa và mô hình máy truy cập ngẫu nhiên.
    • Xây dựng độ đo khoảng cách trực tiếp trên dàn giao khái niệm (FCA) kết hợp lý thuyết Dempster-Shafer (hàm khối, biến đổi Möbius, luật kết hợp Dempster) cho bài toán phân loại đa nhãn đồ thị mà không cần chuyển đổi đồ thị thành véctơ.

  3. Kiến nghị và giải pháp ứng dụng thực tiễn:

    • Các thuật toán đề xuất có thể áp dụng trực tiếp cho các bài toán phân tích dữ liệu lớn dạng bảng và dạng đồ thị trong y tế, hóa tin học, sinh tin học, an ninh mạng và phân tích mạng xã hội.
    • Để ứng dụng vào dữ liệu thực tế ngoài đời thực, văn bản nhấn mạnh quy trình bắt buộc phải thực hiện các công đoạn tiền xử lý, làm sạch dữ liệu và biến đổi dữ liệu về dạng biểu diễn chuẩn tắc trước khi áp dụng các giải thuật của luận án.

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

Văn bản luận án nêu rõ các giới hạn phạm vi và định hướng nghiên cứu:

  • Hạn chế:
    • Các giải thuật xử lý dữ liệu bảng (rút gọn thuộc tính, rút gọn đối tượng, sinh cây quyết định) được xây dựng trên giả định bảng quyết định là nhất quán; đối với bảng không nhất quán cần thực hiện bước tiền xử lý loại bỏ các đối tượng mâu thuẫn để đưa về bảng nhất quán.
    • Các thuật toán trên đồ thị đòi hỏi cơ sở dữ liệu đồ thị phải có tập nhãn đỉnh và cạnh có thứ tự tổng quát $\succeq$, đồ thị được chuẩn hóa theo ma trận kề dạng chuẩn CAM và mô hình tính toán truy cập ngẫu nhiên.
    • Thử nghiệm mới thực hiện trên các bộ dữ liệu nghiên cứu chuẩn đã được làm sạch (UCI, NCI), chưa thử nghiệm trực tiếp trên dữ liệu thô chưa qua tiền xử lý.
  • Hướng nghiên cứu tiếp:
    • Mở rộng các phương pháp rút gọn đối tượng và rút gọn thuộc tính cho các hệ thông tin và bảng quyết định không nhất quán, bảng dữ liệu mờ, hoặc áp dụng mô hình tập thô chính xác biến ($VPRS$).
    • Tối ưu hóa hiệu năng thuật toán PSI-CFSM và kỹ thuật phân loại đa nhãn trên các mạng đồ thị không đồng nhất quy mô cực lớn.

Giá trị tham khảo

Luận án là tài liệu tham khảo cho:

  • Nghiên cứu sinh, học viên cao học và giảng viên ngành Hệ thống thông tin, Khoa học dữ liệu, Khoa học máy tính: Tham khảo cách tích hợp lý thuyết cơ sở dữ liệu quan hệ với lý thuyết tập thô (Chương 1, Chương 2); kỹ thuật chứng minh tính đúng đắn của thuật toán rút gọn dữ liệu bằng đại số Sperner và quan hệ phụ thuộc hàm; kỹ thuật phân tích khái niệm chính thức (FCA) kết hợp lý thuyết Dempster-Shafer (Chương 3).
  • Kỹ sư phát triển phần mềm và chuyên gia xử lý dữ liệu: Tham khảo thuật toán rút gọn dữ liệu hai chiều (thuộc tính và đối tượng) nhằm giảm không gian lưu trữ và tăng tốc độ huấn luyện mô hình cây quyết định; tham khảo giải thuật khai phá mẫu đồ thị con thường xuyên đóng và phân loại đa nhãn trên dữ liệu cấu trúc phức tạp (như phân tử hóa học, cấu trúc sinh học, đồ thị mạng).

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

1. Thuật toán tìm một rút gọn thuộc tính đề xuất trong luận án có ưu điểm gì so với các phương pháp trước đây và độ phức tạp tính toán là bao nhiêu? Trả lời: Các phương pháp trước đây thường phải tìm tất cả các rút gọn thuộc tính (độ phức tạp hàm mũ) rồi mới chọn ra một rút gọn, hoặc phải sử dụng tiếp cận heuristic. Thuật toán AnAttributeReduct của luận án tìm được một rút gọn thuộc tính chính xác mà không dùng heuristic, có độ phức tạp thời gian tồi nhất là $O(|C| \cdot |U|^4)$ — hoàn toàn trong thời gian đa thức theo số thuộc tính và số đối tượng.

2. Rút gọn đối tượng bảng quyết định nhất quán được định nghĩa như thế nào và có ý nghĩa gì? Trả lời: Theo Định nghĩa 2.3, rút gọn đối tượng là một bảng con $DS' = (U', C \cup {d}, V, f)$ với $U' \subseteq U$ sao cho tập tất cả các rút gọn thuộc tính được bảo toàn nguyên vẹn ($RED_{U'}(C) = RED_U(C)$) và việc loại bỏ thêm bất kỳ đối tượng nào trong $U'$ cũng sẽ làm thay đổi tập rút gọn thuộc tính. Ý nghĩa là giúp thu nhỏ số hàng của bảng dữ liệu lớn trong thời gian đa thức mà không làm mất thông tin khai phá thuộc tính.

3. Mối quan hệ toán học giữa hệ bằng nhau cực đại $M_d$ và họ các tập tối tiểu $K_d^r$ được thiết lập ra sao? Trả lời: Luận án chứng minh Bổ đề 2.4: $M_d = (K_d^r)^{-1}$, trong đó $M_d$ là hệ bằng nhau cực đại đối với thuộc tính quyết định $d$ trên quan hệ $r$, và $(K_d^r)^{-1}$ là tập các phản khóa của họ các tập tối tiểu $K_d^r$. Tính chất này cùng tính duy nhất của cặp hệ Sperner $(K, K^{-1})$ là nền tảng để thiết kế và chứng minh tính đúng đắn của thuật toán rút gọn đối tượng AnObjectReduct.

4. Luận án giải quyết bài toán phân loại đa nhãn cho dữ liệu đồ thị bằng cách nào khi đồ thị không có biểu diễn véctơ? Trả lời: Tác giả xây dựng dàn giao khái niệm (FCA) từ tập các đồ thị con thường xuyên đóng, sau đó thiết lập độ đo khoảng cách trực tiếp trên dàn giao dựa trên các phần tử infimum và supremum. Tiếp theo, kết hợp biến đổi Möbius và luật kết hợp Dempster-Shafer để tính toán hàm khối và hàm niềm tin trên tập $k$ láng giềng gần nhất, từ đó gán nhãn cho đồ thị mới mà không cần véctơ hóa dữ liệu.

5. Thuật toán PSI-CFSM giải quyết bài toán gì và dựa trên kỹ thuật nào? Trả lời: Thuật toán PSI-CFSM giải quyết bài toán khai phá đồ thị con thường xuyên đóng trên cơ sở dữ liệu đồ thị giao tác. Thuật toán đưa bài toán kiểm tra đẳng cấu đồ thị con về thời gian đa thức bằng cách sử dụng ma trận kề dạng chuẩn $CAM(G)$, thứ tự từ điển chuẩn trên nhãn và cây tìm kiếm CAM Tree / DFS Code Tree trên mô hình máy truy cập ngẫu nhiên.

Kết luận

Luận án tiến sĩ kỹ thuật của tác giả Hoàng Minh Quang đã giải quyết hai vấn đề cốt lõi trong khai phá dữ liệu có cấu trúc: giảm dữ liệu dư thừa và tối ưu hóa thời gian tính toán từ không đa thức về đa thức. Các đóng góp chính bao gồm phát triển thuật toán rút gọn thuộc tính không heuristic ($O(|C| \cdot |U|^4)$), thuật toán rút gọn đối tượng bảo toàn tập rút gọn thuộc tính trên bảng quyết định nhất quán, thuật toán PSI-CFSM khai phá đồ thị con thường xuyên đóng với kiểm tra đẳng cấu trong thời gian đa thức, và phương pháp phân loại đa nhãn đồ thị trên dàn giao khái niệm theo lý thuyết Dempster-Shafer. Các kết quả lý thuyết đều được chứng minh toán học đầy đủ và được kiểm chứng thực nghiệm trên các tập dữ liệu chuẩn UCI và NCI.