Tổng quan về luận án
Khai thác tập mục phổ biến (Frequent Itemset Mining - FIM) đóng vai trò nền tảng trong lĩnh vực Khai phá Dữ liệu (Data Mining) và Khám phá Tri thức (Knowledge Discovery in Databases - KDD). Luận án tiến sĩ toán học của nghiên cứu sinh Nguyễn Duy Hàm với đề tài "Phát triển một số thuật toán hiệu quả khai thác tập mục trên cơ sở dữ liệu số lượng có sự phân cấp các mục" (Chuyên ngành: Cơ sở toán cho tin học, Mã số: 62460110, bảo vệ tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội) là công trình nghiên cứu tiên phong giải quyết bài toán khai phá tri thức trên các hệ thống cơ sở dữ liệu phức hợp đa chiều.
Trong kỷ nguyên bùng nổ dữ liệu lớn, các cơ sở dữ liệu thực tế (như giao dịch thương mại điện tử, hồ sơ y tế, dữ liệu giao thông) không chỉ tồn tại ở dạng nhị phân đơn thuần (chỉ ghi nhận sự xuất hiện 0/1 của mục) mà thường tích hợp hai đặc tính quan trọng: số lượng/giá trị kinh tế (quantitative/utility values) và cấu trúc phân cấp phân loại tự nhiên (taxonomies/item hierarchies). Nghiên cứu định vị tại điểm giao thoa giữa cấu trúc dữ liệu tối ưu và lý thuyết khai phá mẫu nâng cao, giải quyết triệt để sự đánh đổi (trade-off) kinh điển giữa dung lượng bộ nhớ tiêu thụ và thời gian xử lý khi duyệt không gian tìm kiếm tổ hợp bùng nổ lũy thừa $O(2^n)$.
┌────────────────────────────────────────────────────────┐
│ CƠ SỞ DỮ LIỆU SỐ LƯỢNG PHÂN CẤP (HQDB) │
│ - Kết hợp: Số lượng mua + Trọng số lợi ích + Cây Taxonomy │
└───────────────────────────┬────────────────────────────┘
│
┌────────────────────────────────────┼────────────────────────────────────┐
▼ ▼ ▼
┌────────────────────────┐ ┌────────────────────────┐ ┌────────────────────────┐
│ Khai thác FWI & FWUI │ │ Khai thác TRFWUI_k │ │ Khai thác HQDB Nhanh │
│ - Cấu trúc IWS │ │ - Cấu trúc DTab │ │ - Cấu trúc EDBV │
│ - Cấu trúc MBiS │ │ - Cấu trúc DHeap │ │ - Tránh nhân bản DB │
│ - Mảng tra cứu MAP │ │ - Cắt tỉa Top-k nhanh │ │ - Cắt tỉa Cha-Con │
└────────────────────────┘ └────────────────────────┘ └────────────────────────┘
Khoảng trống nghiên cứu then chốt (Research Gaps) được xác định cụ thể:
- Các thuật toán khai thác tập mục phổ biến có trọng số (FWI) và tập mục phổ biến trọng số hữu ích (FWUI) dựa trên định dạng dọc (Vertical format như IT-tree, WIT-tree, MWIT-tree) yêu cầu dung lượng bộ nhớ lớn để lưu trữ danh sách mã giao dịch (tidset), dẫn đến tắc nghẽn hiệu năng khi tính toán phép giao tidset trên các tập dữ liệu thưa quy mô lớn.
- Tiếp cận vector bit động hiện hành (như DBV) vẫn còn lãng phí ô nhớ do chứa nhiều đoạn byte có giá trị bằng 0 ở giữa chuỗi, đồng thời việc xử lý theo từng byte (8-bit) chưa khai phóng tối đa hiệu năng tính toán của kiến trúc máy tính 64-bit hiện đại.
- Bài toán khai thác $k$ nhóm tập mục phổ biến có thứ hạng cao nhất (Top-rank-$k$) mới chỉ dừng lại ở cơ sở dữ liệu nhị phân (như các thuật toán FAE, VTK, NTK, iNTK), hoàn toàn chưa có lời giải tối ưu cho cơ sở dữ liệu số lượng/trọng số hữu ích.
- Việc khai thác trên cơ sở dữ liệu có sự phân cấp mục (HQDB) theo cách tiếp cận truyền thống đòi hỏi chèn trực tiếp các mục cha (ancestor items) vào từng giao dịch, gây bùng nổ kích thước vật lý của cơ sở dữ liệu và lãng phí thời gian tính toán kiểm tra mối quan hệ cha-con.
Các câu hỏi nghiên cứu ($RQ$) và giả thuyết khoa học ($H$):
- $RQ_1$: Làm thế nào để nén cấu trúc tidset ở mức bit tối ưu mà vẫn cho phép thực hiện phép giao tập hợp với độ phức tạp thời gian $O(1)$ trên từng khối dữ liệu?
- $RQ_2$: Có thể xây dựng cơ chế quản lý ngưỡng động để khai thác $k$ nhóm tập mục hữu ích cao nhất mà không cần người dùng chỉ định trước ngưỡng hỗ trợ tối thiểu ($minwus$)?
- $RQ_3$: Bằng phương pháp nào có thể khai thác tập mục đa cấp độ trên cơ sở dữ liệu số lượng mà không cần biến đổi hay nhân bản dữ liệu giao dịch gốc?
- $H_1$: Cấu trúc phân đoạn word liên tiếp (IWS) kết hợp mảng tra cứu bit định sẵn (MAP) sẽ giảm tiêu hao bộ nhớ từ 40% đến 80% và tăng tốc độ xử lý gấp nhiều lần so với cấu trúc DBV trên cơ sở dữ liệu thưa.
- $H_2$: Sử dụng cấu trúc hàng đợi ưu tiên động (DHeap) sẽ giảm số phép kết nối ứng viên từ mức $O(m^2)$ xuống $O(m \log k)$ trong bài toán Top-rank-$k$.
- $H_3$: Cơ chế sinh trực tiếp tidset của nút cha từ phép hợp tidset của các nút con kết hợp vector bit động mở rộng (EDBV) sẽ loại trừ hoàn toàn chi phí tiền xử lý mở rộng cơ sở dữ liệu phân cấp.
Khung lý thuyết của luận án tích hợp Lý thuyết tập mờ và tập thô, Lý thuyết đồ thị và cây cấu trúc, cùng Nguyên lý bao đóng giảm (Downward Closure Property / Anti-monotonicity). Phạm vi thực nghiệm bao quát các bộ dữ liệu chuẩn quốc tế đa dạng về độ dày (dense) và độ thưa (sparse) như RETAIL, BMS-POS, CONNECT, ACCIDENTS và hệ thống dữ liệu doanh nghiệp phân cấp thực tế SALE-FACT (1997, 1998, SYNC) với quy mô hàng trăm nghìn bản ghi.
Literature Review và Positioning
Lịch sử nghiên cứu khai thác tập mục phổ biến bắt đầu với thuật toán kinh điển Apriori của Agrawal & Srikant (1994) dựa trên nguyên lý bao đóng giảm: "Mọi tập con của một tập mục phổ biến đều phải là tập mục phổ biến". Nhược điểm chí mạng của Apriori là quét cơ sở dữ liệu nhiều lần và chi phí sinh tập ứng viên bùng nổ. Để khắc phục, Han et al. (2000) đề xuất FP-Growth và sau đó Grahne et al. (2003) cải tiến với FP-Growth*, nén cơ sở dữ liệu vào cây FP-tree với hai lần quét dữ liệu. Tuy nhiên, việc duyệt FP-tree đệ quy tiêu tốn tài nguyên tính toán lớn.
Một bước chuyển quan trọng xuất hiện khi Zaki (2000) giới thiệu thuật toán Eclat dựa trên tiếp cận cơ sở dữ liệu dọc và cấu trúc cây IT-tree (Itemset Tidset-tree), chỉ cần một lần quét dữ liệu duy nhất để xác định tidset của các 1-itemset và tính toán các tập mục lớn hơn thông qua phép giao tidset. Để tối ưu bộ nhớ, Zaki & Gouda (2003) phát triển dEclat sử dụng diffset (tập hiệu số giao dịch), nhưng diffset chỉ thực sự phát huy tác dụng trên cơ sở dữ liệu dày, trong khi đại đa số dữ liệu thực tế lại là cơ sở dữ liệu thưa.
Trong hướng nghiên cứu cơ sở dữ liệu trọng số và số lượng:
- Ramkumar et al. (1998) đặt nền móng với bài toán luật kết hợp có trọng số.
- Yun & Leggett (2005) đề xuất thuật toán WSPAN sử dụng mô hình maximum-weighted-upper-bound, kết hợp song song trọng số và độ hỗ trợ.
- Tao, Murtagh & Farid (2003) thiết lập hệ tiêu chuẩn mới khi đề xuất hai đại lượng: Trọng số giao dịch ($tw$) tính bằng trung bình cộng trọng số các mục, và Độ hỗ trợ trọng số ($ws$) thỏa mãn tính chất bao đóng giảm một cách tự nhiên.
- Khan et al. (2010) mở rộng sang cơ sở dữ liệu số lượng với hai độ đo cốt lõi: Trọng số hữu ích giao dịch ($twu$) và Độ hỗ trợ trọng số hữu ích ($wus$).
- Võ Đình Bảy et al. (2012, 2013) phát triển các cấu trúc cây WIT-tree và MWIT-tree dựa trên tiếp cận Eclat, giúp khai thác FWI và FWUI chỉ với một lần quét dữ liệu.
TIẾN TRÌNH PHÁT TRIỂN CỦA CÁC PHƯƠNG PHÁP KHAI THÁC TẬP MỤC:
[1994] Apriori (Agrawal) ────────► Quét CSDL nhiều lần, sinh ứng viên lớn
│
[2000] FP-Growth (Han) ──────────► Quét 2 lần, nén FP-tree, duyệt đệ quy phức tạp
│
[2000] Eclat (Zaki) ─────────────► Quét 1 lần, cấu trúc dọc IT-tree, tốn RAM lưu tidset
│
[2003] dEclat (Zaki) ────────────► Cấu trúc Diffset (chỉ tối ưu trên CSDL dày)
│
[2003] W-Apriori (Tao et al.) ───► Khởi xướng độ đo tw/ws, nhưng quét CSDL nhiều lần
│
[2012] WIT/MWIT-tree (Vo et al.) ─► Áp dụng IT-tree cho FWI/FWUI, tốn RAM mảng tidset
│
[2016] CÔNG TRÌNH LUẬN ÁN ──────► Cấu trúc IWS, MBiS, EDBV, DHeap:
Tối ưu Bit-vector 16/64-bit, cắt tỉa không gian phân cấp
Trong hướng tiếp cận vector bit, Luoie & Liu (1998) khởi xướng ý tưởng, sau đó Dong & Han (2007) và Song et al. (2007) chuẩn hóa cấu trúc BitTable. Cấu trúc này dùng $(\lceil |T|/8 \rceil)$ byte cho mỗi tập mục và áp dụng phép toán bitwise AND. Võ Đình Bảy et al. (2010) nâng cấp thành DBV (Dynamic Bit-Vector), cắt bỏ các byte 0 thừa ở đầu và cuối chuỗi. Tuy nhiên, DBV vẫn giữ lại toàn bộ các byte 0 ở giữa.
Đối với bài toán phân cấp, Han & Fu (1995) và Srikant & Agrawal (1995) mở đầu cho khai thác luật đa cấp độ. Liu et al. (1999) và Tseng et al. (2007) đề xuất khai thác với nhiều ngưỡng hỗ trợ khác nhau theo mô hình Apriori. Võ Đình Bảy et al. (2013) mở rộng Eclat với cấu trúc GIT-tree. Điểm yếu chung của các nghiên cứu quốc tế này là bắt buộc phải chèn mục cha vào từng giao dịch, khiến kích thước cơ sở dữ liệu tăng vọt từ kích thước $T \times |I|$ ban đầu lên $T \times (|I| + |J|)$.
Luận án của Nguyễn Duy Hàm đã định vị xuất sắc khi khắc phục toàn bộ các điểm nghẽn trên: loại bỏ hoàn toàn các word 0 trung gian thông qua cấu trúc IWS/MBiS, thiết lập cơ chế khai thác Top-rank-$k$ trên CSDL số lượng với cấu trúc Heap động, và giải quyết bài toán phân cấp đa cấp độ mà không cần thay đổi kích thước cơ sở dữ liệu ban đầu.
Đóng góp lý thuyết và khung phân tích
Đóng góp cho lý thuyết
Luận án mở rộng nền tảng lý thuyết khai phá dữ liệu thông qua việc chuẩn hóa toán học các khái niệm trên Cơ sở dữ liệu số lượng có sự phân cấp (Hierarchical Quantitative Database - HQDB):
"Cơ sở dữ liệu số lượng (quantitative database) là một bộ ba thành phần: $T, I, W$, trong đó $T = {t_1, t_2, \dots, t_m}$ là tập gồm $m$ giao dịch; $I = {i_1, i_2, \dots, i_n}$ là tập gồm $n$ mục; $W = {w_1, w_2, \dots, w_n}$ là tập gồm $n$ trọng số của các mục tương ứng trong tập $I$."
Luận án hoàn thiện hệ thống công thức toán học xác định trọng số và độ hỗ trợ hữu ích:
- Trọng số giao dịch ($tw$):
$$tw(t_k) = \frac{\sum_{i_j \in t_k} w_j}{|t_k|}$$
- Độ hỗ trợ trọng số ($ws$) của tập mục $X$:
$$ws(X) = \frac{\sum_{t_k \in t(X)} tw(t_k)}{\sum_{k=1}^m tw(t_k)}$$
- Trọng số hữu ích giao dịch ($twu$):
$$twu(t_k) = \frac{\sum_{i=1}^n q(i, t_k) \cdot w_i}{\sum_{i=1}^n q(i, t_k)}$$
- Độ hỗ trợ trọng số hữu ích ($wus$) của tập mục $X$:
$$wus(X) = \frac{\sum_{t_k \in T(X)} twu(t_k)}{\sum_{k=1}^m twu(t_k)}$$
Hệ thống mệnh đề lý thuyết cốt lõi được chứng minh chặt chẽ:
- Mệnh đề 1 (Tính bao đóng giảm của $wus$): Với mọi tập mục $X, Y \subseteq I$, nếu $X \subset Y$ thì $T(Y) \subseteq T(X)$, kéo theo $wus(Y) \le wus(X)$. Do đó, nếu $wus(X) < minwus$ thì mọi siêu tập $Y \supset X$ đều thỏa mãn $wus(Y) < minwus$ và bị cắt tỉa an toàn.
- Mệnh đề 2 (Đoạn con trong IWS): Đoạn $S_x = s_x(w_{x1}, \dots, w_{xk})$ là đoạn con của $S_y = s_y(w_{y1}, \dots, w_{yl})$ khi và chỉ khi $s_y \le s_x$ và $s_x + k \le s_y + l$, đồng thời các giá trị word tương ứng đồng nhất.
- Mệnh đề 3 (Giao hai đoạn IWS): Giao của hai đoạn $S_x$ và $S_y$ là đoạn $S_z = S_x \cap S_y$ có vị trí bắt đầu $s_z = \max(s_x, s_y)$, độ dài $m = \min(k+s_x, l+s_y) - s_z$, và các phần tử $w_{zj} = w_{x(j+s_z-s_x)} \text{ AND } w_{y(j+s_z-s_y)}$.
CẤU TRÚC PHÂN TÍCH VÀ QUAN HỆ KẾ THỪA TRONG LUẬN ÁN:
┌────────────────────────────────────────┐
│ NGUYÊN LÝ BAO ĐÓNG GIẢM │
│ ∀ X ⊂ Y ⟹ wus(Y) ≤ wus(X) │
└───────────────────┬────────────────────┘
│
┌───────────────────────┴───────────────────────┐
▼ ▼
┌───────────────────────────────┐ ┌───────────────────────────────┐
│ BIỂU DIỄN BIT-VECTOR │ │ QUẢN TRỊ CÂY PHÂN CẤP │
│ - IWS: Bỏ toàn bộ word 0 │ │ - Không nhân bản mục cha │
│ - MBiS: Lưu cặp biên [L, R] │ │ - tidset(P) = ∪ tidset(C_i) │
│ - EDBV: Mở rộng word 64-bit │ │ - Cắt tỉa quan hệ Cha - Con │
└──────────────┬────────────────┘ └──────────────┬────────────────┘
│ │
└───────────────────┬───────────────────┘
│
▼
┌─────────────────────────────────────────────────────┐
│ CÁC THUẬT TOÁN TỐI ƯU: │
│ - IWS-tree / MBiS-tree (Khai thác FWI/FWUI nhanh) │
│ - TRFWUI_k với DTab & DHeap (Top-k hữu ích) │
│ - Fast-FWUI trên HQDB (Khai thác đa cấp tối ưu) │
└─────────────────────────────────────────────────────┘
Khung phân tích độc đáo
Luận án kiến tạo 5 cấu trúc dữ liệu đột phá:
- Interval Word Segment (IWS): Biểu diễn tidset dưới dạng danh sách các đoạn word 16-bit (2 bytes) liên tiếp khác 0. Cấu trúc này giải quyết triệt để hạn chế lưu trữ của DBV khi loại bỏ 100% các khối word mang giá trị 0 ở bất kỳ vị trí nào trên chuỗi bit.
- Mảng tra cứu tiền xử lý MAP ($2^{16} = 65,536$ phần tử): Khởi tạo sẵn danh sách vị trí các bit 1 cho từng giá trị word từ 0 đến 65535. Khi thực hiện phép giao hai IWS, thuật toán chỉ cần tra bảng MAP một lần để trích xuất ngay chỉ số các giao dịch hợp lệ, triệt tiêu hoàn toàn các vòng lặp kiểm tra bit riêng lẻ.
- Multi Bits Segment (MBiS): Nén các chuỗi bit 1 liên tiếp thành các đoạn có vị trí đầu và vị trí cuối. Phép giao hai MBiS quy về phép so sánh cực đại ($\max$) đầu đoạn và cực tiểu ($\min$) cuối đoạn, đạt tốc độ tiệm cận tức thời.
- Cấu trúc bảng động (DTab) và Heap động (DHeap): Duy trì danh sách $k$ nhóm có $wus$ cao nhất theo cơ chế hàng đợi ưu tiên min-heap. Ngưỡng cắt tỉa $minwus$ được nâng động liên tục theo giá trị phần tử gốc của DHeap, loại bỏ sớm hơn 90% không gian tìm kiếm dư thừa.
- Extended Dynamic Bit-Vector (EDBV): Ứng dụng cấu trúc số nguyên lớn (Large Integer - 64 bit / 8 byte) để biểu diễn giao dịch cho CSDL phân cấp, cho phép thực thi phép toán hợp tidset của các nút con nhằm suy ra tidset của nút cha:
$$tidset(\text{Parent}) = \bigcup_{i} tidset(\text{Child}_i)$$
Phương pháp nghiên cứu tiên tiến
Thiết kế nghiên cứu
Công trình được xây dựng trên lập trường triết học thực chứng (Positivism) và nhận thức luận duy lý logic toán học. Phương pháp nghiên cứu kết hợp giữa mô hình hóa hình thức (Formal Mathematical Modeling), thiết kế giải thuật nâng cao (Algorithm Engineering) và kiểm định thực chứng nghiêm ngặt (Empirical Benchmarking).
QUY TRÌNH THỰC NGHIỆM VÀ ĐÁNH GIÁ ĐỘ PHỨC TẠP:
┌────────────────────────┐ ┌────────────────────────┐ ┌────────────────────────┐
│ TẬP DỮ LIỆU CHUẨN │ │ MÔI TRƯỜNG THỬ MÃ │ │ CHỈ SỐ ĐO LƯỜNG │
│ - RETAIL (88.162 trans)│ │ - C++ GNU GCC 64-bit │ │ - Thời gian chạy (s) │
│ - BMS-POS (515.597 tr) │ ───► │ - Intel Core i5 / RAM │ ───► │ - Đỉnh bộ nhớ (RAM MB) │
│ - CONNECT (67.557 tr) │ │ - Linux Ubuntu OS │ │ - Tỷ lệ cắt tỉa nhánh │
│ - SALE-FACT (Phân cấp) │ │ - Đa dạng ngưỡng minws │ │ - Tốc độ nén bit-vector│
└────────────────────────┘ └────────────────────────┘ └────────────────────────┘
Thiết kế thực nghiệm phân tầng dữ liệu:
- Tầng dữ liệu thưa (Sparse Datasets): RETAIL (88.162 giao dịch, 16.470 mục), BMS-POS (515.597 giao dịch, 1.657 mục).
- Tầng dữ liệu dày (Dense Datasets): CONNECT (67.557 giao dịch, 129 mục), ACCIDENTS (340.183 giao dịch, 468 mục).
- Tầng dữ liệu đa cấp phân cấp thực tế: SALE-FACT-1997, SALE-FACT-1997+1998, SALE-FACT-SYNC với cây phân cấp sản phẩm đa tầng.
Quy trình nghiên cứu rigorous
Quy trình nghiên cứu trải qua 4 giai đoạn khép kín:
- Thiết kế toán học và chứng minh tính đúng đắn: Mọi giải thuật đều được chứng minh tính đầy đủ (completeness - không bỏ sót mẫu phổ biến) và tính đúng đắn (correctness - không sinh mẫu rác) dựa trên đại số Boolean và lý thuyết dàn (Lattice Theory).
- Tối ưu hóa cấu trúc dữ liệu mức phần cứng: Chuyển dịch toàn bộ cấu trúc từ dạng mảng con trỏ danh sách liên kết truyền thống sang mảng bit nguyên khối tương thích thanh ghi CPU 64-bit và bộ nhớ đệm Cache L1/L2.
- Triển khai lập trình thực nghiệm: Thuật toán được cài đặt hoàn toàn bằng ngôn ngữ C++ hiệu năng cao, biên dịch trên nền tảng Linux 64-bit, đảm bảo tính đồng nhất môi trường khi so sánh trực diện với các thuật toán đối sánh.
- Kiểm tra chéo và đối chuẩn (Cross-validation Benchmarking): So sánh đối đầu đa chỉ số (thời gian tính toán CPU time tính bằng giây, dung lượng bộ nhớ thực tế tính bằng MegaBytes) trên cùng các ngưỡng hỗ trợ suy giảm liên tục.
Data và phân tích
| Tên CSDL | Đặc tính CSDL | Số giao dịch ($|T|$) | Số lượng mục ($|I|$) | Độ dài TB giao dịch |
| :--- | :--- | :--- | :--- | :--- |
| RETAIL | Thưa (Sparse) | 88.162 | 16.470 | 10,3 |
| BMS-POS | Thưa (Sparse) | 515.597 | 1.657 | 6,5 |
| CONNECT | Rất dày (Very Dense) | 67.557 | 129 | 43,0 |
| ACCIDENTS | Dày (Dense) | 340.183 | 468 | 33,8 |
| SALE-FACT-1997 | Số lượng có phân cấp | 86.829 | 1.560 | 4,2 |
| SALE-FACT-SYNC | Số lượng có phân cấp | 250.000 | 2.150 | 5,8 |
Phân tích hiệu năng chỉ ra rằng:
- Khi ngưỡng $minws$ giảm dần từ 0,05 xuống 0,001 trên CSDL RETAIL, cấu trúc IWS-tree duy trì thời gian thực thi ổn định vượt trội so với WIT-tree và DBV-tree.
- Thuật toán khai thác FWUI dựa trên MBiS-tree giảm tới 75% chi phí bộ nhớ so với MWIT-tree trên bộ dữ liệu BMS-POS.
- Thuật toán TRFWUIk sử dụng DHeap giải quyết hoàn toàn bài toán quá tải bộ nhớ của thuật toán VTK và iNTK khi tham số $k$ tăng từ 5 lên 100.
Phát hiện đột phá và implications
Những phát hiện then chốt
- Khắc phục triệt để hiện tượng phân mảnh bộ nhớ của DBV:
"Cấu trúc IWS loại bỏ hoàn toàn các word có giá trị bằng 0 khỏi DBV, bằng cách này đã giải quyết được hạn chế về lãng phí bộ nhớ của DBV."
Trên các cơ sở dữ liệu cực thưa như RETAIL và BMS-POS, số lượng word có giá trị bằng 0 chiếm từ 60% đến 85% tổng chiều dài chuỗi bit. IWS nén toàn bộ không gian này, chỉ lưu trữ các đoạn hữu hiệu.
SO SÁNH CÁC CẤU TRÚC BIỂU DIỄN TIDSET TRÊN CƠ SỞ DỮ LIỆU:
1. DBV (Dynamic Bit-Vector):
┌───────┬───────────────────────────────────────────┬───────┐
│ 0 0 0 │ 6 9 0 0 0 1 5 1 4 6 0 0 0 0 │ 0 0 0 │ ──► Cắt 0 ở 2 đầu,
└───────┴───────────────────────────────────────────┴───────┘ giữ nguyên 0 ở giữa
2. IWS (Interval Word Segment - Đề xuất):
┌───────────────┬───────────────────────────┬───────────────┐
│ Đoạn 1 (Pos 3)│ Đoạn 2 (Pos 5 - 3 words) │ Đoạn 3(Pos 12)│ ──► Loại bỏ 100%
│ Word: [1545] │ Words: [1, 1281, 1030] │ Words: [1...] │ các word 0
└───────────────┴───────────────────────────┴───────────────┘
3. MBiS (Multi-Bit Segment - Đề xuất):
┌───────────────┬───────────────────────────┬───────────────┐
│ [Start1, End1]│ [Start2, End2] │ [Start3, End3]│ ──► Chỉ lưu vị trí
│ Bit 1 liên tục│ Bit 1 liên tục │ Bit 1 liên tục│ đầu-cuối bit 1
└───────────────┴───────────────────────────┴───────────────┘
-
Tăng tốc độ tính toán nhờ mảng MAP $2^{16}$:
Việc chuyển đổi từ kiểm tra bit tuần tự sang tra cứu trực tiếp qua mảng MAP gồm 65.536 phần tử giúp tốc độ xác định các giao dịch chứa tập mục tăng gấp 4 đến 6 lần so với phương pháp dịch bit thông thường.
-
Cơ chế suy diễn tidset nút cha loại bỏ hoàn toàn việc mở rộng cơ sở dữ liệu vật lý:
Trong CSDL phân cấp, thay vì phải chèn các mục cha vào từng bản ghi (làm tăng kích thước cơ sở dữ liệu từ 11 mục lên 21 mục như trong ví dụ minh họa của luận án), thuật toán EDBV chỉ cần tính hợp tidset của các nút con ở mức dưới. Nhờ đó, kích thước CSDL trên RAM giảm hơn 50%, loại bỏ hoàn toàn nguy cơ tràn bộ nhớ.
-
Hiệu năng vượt trội của DHeap trong khai thác Top-rank-$k$:
Khác với thuật toán VTK (phải kết nối toàn bộ $m(m-1)/2$ cặp tập mục), thuật toán đề xuất chỉ duyệt cây TR-tree kết hợp DHeap để cập nhật ngưỡng cắt tỉa tức thời, giảm thời gian xử lý xuống từ 3 đến 8 lần trên cơ sở dữ liệu CONNECT và ACCIDENTS.
Implications đa chiều
- Về mặt Lý thuyết: Đặt nền móng vững chắc cho lý thuyết khai phá mẫu trên cấu trúc phân cấp số lượng (HQDB Mining Theory), mở rộng ranh giới của các cấu trúc dạng dọc (Vertical Data Mining).
- Về mặt Phương pháp luận: Chứng minh ưu thế tuyệt đối của tiếp cận lai (Hybrid Bit-vector & Tree Lattice) trong việc tối ưu hóa hiệu năng tính toán thuật toán trên cấu trúc máy tính hiện đại.
- Về mặt Thực tiễn Doanh nghiệp: Cho phép các hệ thống bán lẻ (Retail Analytics), siêu thị lớn xử lý trực tiếp dữ liệu hóa đơn giao dịch theo thời gian thực (Real-time Transaction Analysis), phân tích giỏ hàng (Market Basket Analysis) ở các mức độ trừu tượng khác nhau (từ mã sản phẩm cụ thể đến nhóm hàng, ngành hàng).
- Về mặt Chính sách và Quản lý: Hỗ trợ đắc lực cho các hệ sinh thái y tế số trong việc phân tích các ca bệnh phức hợp đa triệu chứng có trọng số và phân loại bệnh học quốc tế (ICD).
Limitations và Future Research
Luận án thừa nhận một số giới hạn học thuật và điều kiện biên:
- Giới hạn cấu trúc dữ liệu dày: Trên các cơ sở dữ liệu có mật độ cực dày (như CONNECT với độ dài giao dịch trung bình 43/129 mục), cấu trúc IWS và MBiS không phát huy tối đa hiệu quả nén do số lượng đoạn phân tách tăng cao, khiến chi phí quản lý con trỏ đoạn tiệm cận với bit-vector tiêu chuẩn.
- Cơ sở dữ liệu tĩnh (Static Database Assumption): Các thuật toán được thiết kế tối ưu cho cơ sở dữ liệu tĩnh, chưa tích hợp cơ chế cập nhật gia tăng (Incremental Mining) khi có luồng giao dịch mới xuất hiện liên tục.
- Mô hình phân cấp đơn nhánh: Cây phân cấp giả định mỗi mục con chỉ có duy nhất một mục cha trực tiếp (Tree taxonomy), chưa bao quát toàn diện mô hình đồ thị có hướng không chu trình (DAG Taxonomies / Multi-parent ontologies).
Chương trình nghiên cứu mở rộng trong tương lai:
- Hướng 1: Mở rộng thuật toán cho bài toán khai thác trên luồng dữ liệu (Data Streams) và cập nhật dữ liệu gia tăng trực tuyến.
- Hướng 2: Tích hợp thuật toán IWS/MBiS vào các khung tính toán phân tán quy mô lớn như Apache Spark, GPU CUDA và môi trường Điện toán Đám mây.
- Hướng 3: Khai phá tập mục hữu ích cao (High Utility Pattern Mining) kết hợp trọng số âm và khoảng thời gian hiệu lực (Time-interval Quantitative Itemsets).
- Hướng 4: Xử lý dữ liệu phân cấp không chắc chắn (Uncertain & Probabilistic Hierarchical Databases).
Tác động và ảnh hưởng
Công trình luận án mang lại giá trị học thuật và ứng dụng thực tiễn to lớn:
- Tác động học thuật: Các kết quả nghiên cứu cốt lõi của luận án đã được công bố tại các diễn đàn khoa học quốc tế uy tín như Hội thảo Quốc tế IEEE SMC (IEEE International Conference on Systems, Man, and Cybernetics, 2015) và các tạp chí khoa học chuyên ngành trong nước và quốc tế.
- Chuyển đổi công nghiệp: Cung cấp thuật toán lõi cho các công cụ BI (Business Intelligence), hệ thống khuyến nghị (Recommender Systems), tối ưu hóa chuỗi cung ứng và định giá bán lẻ đa cấp.
- Lợi ích xã hội: Hỗ trợ phân tích dữ liệu vi phạm an toàn giao thông và phân loại triệu chứng lâm sàng trong y tế cộng đồng, giúp các cơ quan quản lý đưa ra quyết định dựa trên dữ liệu chuẩn xác.
Đối tượng hưởng lợi
- Nghiên cứu sinh & Giới học thuật: Tiếp cận các chứng minh toán học chuẩn mực, mô hình cấu trúc dữ liệu bit-vector tối ưu, mở ra các hướng nghiên cứu phái sinh về khai phá mẫu nâng cao.
- Kỹ sư Hệ thống Dữ liệu & R&D: Ứng dụng trực tiếp mã nguồn giải thuật C++, các cấu trúc IWS, MBiS, DHeap vào việc tối ưu hóa các module truy vấn dữ liệu lớn và khai phá mẫu thường xuyên trong các sản phẩm thương mại.
- Doanh nghiệp Bán lẻ & Thương mại Điện tử: Nắm bắt quy luật mua hàng đa cấp độ của người tiêu dùng, tối ưu hóa danh mục tồn kho và nâng cao doanh thu từ các chương trình khuyến mãi chéo (Cross-selling).
Câu hỏi chuyên sâu
1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nào?
Đóng góp độc đáo nhất là việc xây dựng hệ hình toán học cho bài toán khai thác tập mục phổ biến trọng số hữu ích trên cơ sở dữ liệu số lượng có sự phân cấp (HQDB). Luận án đã mở rộng lý thuyết khai phá mẫu dọc (Vertical Mining Framework của Zaki) và nguyên lý độ đo hữu ích ($twu/wus$ của Khan et al.) lên không gian cấu trúc phân cấp đa tầng, chứng minh tính bảo toàn của nguyên lý bao đóng giảm khi thực hiện phép chiếu tập mục trên cây phân cấp mà không cần mở rộng vật lý cơ sở dữ liệu.
2. Sự đổi mới về mặt phương pháp luận so với các nghiên cứu quốc tế tiền nhiệm?
So với cấu trúc IT-tree (Zaki 2000), WIT-tree (Võ Đình Bảy et al. 2012) vốn dùng danh sách mảng tốn bộ nhớ, và DBV (Võ Đình Bảy et al. 2010) vốn vẫn giữ lại các byte 0 ở giữa chuỗi bit, luận án đã đổi mới triệt để phương pháp luận biểu diễn dữ liệu:
- Đề xuất IWS loại bỏ 100% các khối word 0 trung gian.
- Đề xuất MBiS chuyển đổi phép toán giao tập hợp phức tạp thành bài toán so sánh biên độ đơn giản trên các đoạn bit 1 liên tiếp.
- Thay thế toàn bộ quá trình kiểm tra bit bằng mảng tra cứu MAP $2^{16}$ hằng số $O(1)$.
3. Phát hiện bất ngờ nhất trong quá trình thực nghiệm là gì?
Phát hiện thực nghiệm quan trọng là trên các cơ sở dữ liệu cực thưa (như RETAIL với hơn 16.000 mục nhưng độ dài giao dịch chỉ 10 mục), cấu trúc IWS giúp nén không gian bộ nhớ lưu trữ tidset lên đến hơn 80% so với IT-tree, đồng thời thời gian thực thi của thuật toán MBiS-tree nhanh hơn MWIT-tree từ 3 đến 5 lần tại các ngưỡng hỗ trợ rất thấp (nơi số lượng tập mục phổ biến bùng nổ mạnh nhất).
4. Luận án có cung cấp quy trình tái lập (Replication Protocol) không?
Luận án cung cấp chi tiết toàn bộ mã giả (Pseudocode) của các thuật toán: Thuật toán xác định giao hai IWS, Thuật toán khai thác FWI trên IWS-tree, Thuật toán xác định giao hai MBiS, Thuật toán khai thác FWUI trên MBiS-tree, Thuật toán TRFWUIk với DTab/DHeap, và Thuật toán Fast-FWUI trên HQDB. Các bộ dữ liệu thử nghiệm đều là dữ liệu chuẩn công khai của quốc tế (FIMI Repository) hoặc dữ liệu doanh nghiệp đã chuẩn hóa, cho phép tái lập 100% kết quả thực nghiệm.
5. Chương trình nghiên cứu 10 năm tiếp theo được định hình ra sao?
Chương trình 10 năm tập trung vào 3 trụ cột: (1) Thiết kế cấu trúc dữ liệu phần cứng hóa (Hardware-accelerated Data Structures) khai thác tập lệnh SIMD/AVX-512 trên chip hiện đại; (2) Phát triển các thuật toán khai phá đồ thị phân cấp quy mô lớn (Large-scale Hierarchical Graph Mining); (3) Tích hợp học máy tự động (AutoML) để tối ưu hóa việc tự động điều chỉnh ngưỡng phân cấp theo phân phối xác suất của dữ liệu giao dịch thực tế.
Kết luận
Luận án tiến sĩ của tác giả Nguyễn Duy Hàm đã hoàn thành xuất sắc toàn bộ các mục tiêu khoa học đề ra, tạo nên bước đột phá toàn diện trong lĩnh vực khai phá tập mục phổ biến trên cơ sở dữ liệu số lượng có sự phân cấp.
Các đóng góp cụ thể của công trình bao gồm:
- Phát triển cấu trúc IWS và mảng MAP $2^{16}$: Giải quyết dứt điểm vấn đề lãng phí bộ nhớ của vector bit động (DBV), tối ưu hóa tốc độ tính giao tidset trên CSDL thưa.
- Đề xuất cấu trúc MBiS và MBiS-tree: Tăng tốc độ khai thác tập mục phổ biến trọng số hữu ích (FWUI) thông qua việc quản lý các dải bit 1 liên tiếp.
- Mô hình hóa và giải quyết bài toán Top-rank-$k$ trên CSDL số lượng: Thiết kế thành công hai thuật toán hiệu năng cao dựa trên bảng động DTab và heap động DHeap.
- Xây dựng khung giải thuật khai phá CSDL số lượng phân cấp (HQDB): Loại bỏ hoàn toàn chi phí nhân bản cơ sở dữ liệu thông qua cấu trúc EDBV và cơ chế suy diễn tidset từ con lên cha.
- Đóng góp vào kho tàng khoa học quốc tế: Hệ thống thuật toán được kiểm chứng nghiêm ngặt, công bố trên các kỷ yếu hội nghị IEEE quốc tế và tạp chí chuyên ngành uy tín.
- Mở ra các hướng nghiên cứu hiện đại: Thiết lập nền tảng vững chắc cho các bài toán phân tích dữ liệu lớn, tính toán phân tán và khai phá tri thức doanh nghiệp trong tương lai.
