Tổng quan luận án

Tính cấp thiết và khoảng trống nghiên cứu

Trong lĩnh vực khai thác dữ liệu (data mining), bài toán khai thác tập mục phổ biến (Frequent Itemset - FI) đóng vai trò nền tảng để trích xuất các luật kết hợp, hỗ trợ dự báo và ra quyết định trong các hệ thống thông tin thực tế như thương mại điện tử, siêu thị, quản lý giao thông và y tế. Các thuật toán khai thác FI kinh điển như Apriori (Agrawal và cộng sự, 1994), FP-Growth (Han và cộng sự, 2000), hay Eclat (Zaki, 2000) chủ yếu tập trung vào cơ sở dữ liệu nhị phân (Binary Database - BDB). Tuy nhiên, dữ liệu thực tế phần lớn chứa các thông tin về số lượng và trọng số của các mặt hàng (Quantitative Database - QDB), hoặc biểu diễn quan hệ ngữ nghĩa giữa các mục thông qua cây phân cấp (Hierarchical Database - HDB).

Khai thác tập mục phổ biến có trọng số (Frequent Weighted Itemset - FWI) và khai thác tập mục phổ biến trọng số hữu ích (Frequent Weighted Utility Itemset - FWUI) trên cơ sở dữ liệu số lượng đã được đặt ra nhằm phản ánh chính xác tầm quan trọng của từng mục và từng giao dịch. Mặc dù vậy, các kỹ thuật hiện có (như cấu trúc WIT-tree, MWIT-tree hoặc kỹ thuật diffset) vẫn gặp phải rào cản lớn về chi phí bộ nhớ lưu trữ tập các chỉ số giao dịch (tidset) và thời gian tính toán giao tập hợp, đặc biệt trên các cơ sở dữ liệu thưa. Bên cạnh đó, 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$ Frequent Itemset - $\text{TRFI}_k$) mới chỉ được nghiên cứu trên cơ sở dữ liệu nhị phân mà chưa được mở rộng sang cơ sở dữ liệu số lượng ($\text{TRFWUI}_k$). Mặt khác, đối với cơ sở dữ liệu có sự phân cấp các mục, các phương pháp hiện hành thường phải chèn toàn bộ các mục cha vào từng giao dịch, dẫn đến sự bùng nổ về dung lượng lưu trữ và thời gian duyệt cây. Đặc biệt, bài toán khai thác 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 mục (Hierarchical Quantitative Database - HQDB) – nơi kết hợp đồng thời cả số lượng, trọng số và phân cấp ngữ nghĩa – hoàn toàn chưa được quan tâm nghiên cứu đầy đủ.

Mục tiêu nghiên cứu

Luận án xác định ba mục tiêu nghiên cứu cụ thể:

  1. Đề xuất một số cấu trúc dữ liệu mới, thuật toán mới để nâng cao hiệu quả khai thác FWI và FWUI trên cơ sở dữ liệu số lượng. Từ đó áp dụng cho khai thác 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 mục.
  2. Đề xuất thuật toán hiệu quả để khai thác $k$ nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất ($\text{TRFWUI}_k$) trên cơ sở dữ liệu số lượng.
  3. Đề xuất cấu trúc dữ liệu, thuật toán hiệu quả để khai thác FWUI trên cơ sở dữ liệu số lượng có sự phân cấp các mục.

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

  • Đối tượng nghiên cứu: Các mô hình cơ sở dữ liệu giao dịch (BDB, WDB, QDB, HDB, HQDB), các cấu trúc dữ liệu biểu diễn tidset (bit-vector, DBV, MByS, IWS, MBiS, EDBV, DTab, DHeap), và các giải thuật khai thác tập mục phổ biến (FI, FWI, FWUI, $\text{TRFWUI}_k$).
  • Phạm vi nghiên cứu:
    • Về mặt lý thuyết: Tập trung vào các phương pháp khai thác theo chiều dọc (vertical data format) dựa trên mở rộng cây IT-tree và kỹ thuật xử lý bitwise nhằm tối ưu hóa bộ nhớ và thời gian xử lý; nghiên cứu cơ chế khai thác thỏa mãn tính chất bao đóng giảm (downward closure property) của độ hỗ trợ trọng số ($ws$) và độ hỗ trợ trọng số hữu ích ($wus$).
    • Về mặt thực nghiệm: Đánh giá hiệu năng trên các tập dữ liệu chuẩn quốc tế và tập dữ liệu bán lẻ thực tế (RETAIL, BMS_POS, CONNECT, ACCIDENTS, SALE_FACT_1997, SALE_FACT_1997+1998, SALE_FACT_SYNC).

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

Các hướng nghiên cứu trước được điểm lại trong luận án

Luận án hệ thống hóa các hướng tiếp cận chính trong lịch sử phát triển bài toán khai thác tập mục:

Hướng nghiên cứu Tác giả & Công trình tiêu biểu Đặc điểm & Hạn chế chính
Khai thác FI trên CSDL ngang Agrawal và cs. (1993, 1994) [1, 2] - Thuật toán Apriori; Han và cs. (2000) [20] - FP-Growth; Grahne và cs. [16] - FP-Growth*. Apriori phải quét CSDL nhiều lần và sinh số lượng lớn ứng viên. FP-Growth nén dữ liệu lên cây FP-tree chỉ cần 2 lần quét CSDL nhưng mất nhiều thời gian duyệt cây đệ quy; khó áp dụng cho CSDL số lượng.
Khai thác FI trên CSDL dọc Zaki và cs. (2000) [54] - Thuật toán Eclat (IT-tree); Zaki và Gouda (2003) [55] - Cấu trúc diffset (dEclat). Eclat chỉ quét CSDL 1 lần để chuyển sang dạng dọc nhưng tốn bộ nhớ lưu trữ tidset. Diffset dùng phần bù tidset để tiết kiệm bộ nhớ nhưng chỉ hiệu quả trên CSDL dày, kém hiệu quả trên CSDL thưa.
Khai thác FWI trên WDB Ramkumar và cs. (1998) [37] - Thuật toán WIS; Yun và cs. (2003) [50], Yun & Leggett (2005) [51] - WSPAN; Lan và cs. (2014) [24]; Tao và cs. (2003) [39]; Le (2012) [27]; Vo và cs. (2012, 2013) [42, 43] - WIT-tree. Hướng tiếp cận dùng hàm trung bình tính trọng số không đảm bảo tính bao đóng giảm. Hướng dùng trọng số giao dịch ($tw$) và độ hỗ trợ trọng số ($ws$) của Tao thỏa mãn bao đóng giảm nhưng theo hướng Apriori nên quét CSDL nhiều lần. Hướng dùng WIT-tree khắc phục số lần quét nhưng tốn bộ nhớ lưu tidset.
Khai thác FWUI trên QDB Khan và cs. (2002) [22]; Vo và cs. (2013) [44] - MWIT-tree. Khan đề xuất độ đo $twu$ và $wus$. MWIT-tree mở rộng IT-tree để khai thác FWUI với 1 lần quét CSDL nhưng dung lượng bộ nhớ dành cho danh sách tidset vẫn rất lớn.
Khai thác Top-rank-$k$ ($\text{TRFI}_k$) Deng và cs. (2007, 2012) [8, 10, 11] - Thuật toán FAE, NTK; Fang và cs. (2006) [15] - Thuật toán VTK; Le và cs. (2014) [28] - Thuật toán iNTK (dựa trên N-list). Mới chỉ giải quyết trên CSDL nhị phân. VTK tốn bộ nhớ lưu tidset và tốn thời gian nối bảng; NTK và iNTK cải thiện bộ nhớ nhưng vẫn phải quét CSDL 2 lần tạo cây PPC-tree. Chưa có giải pháp cho CSDL số lượng.
Khai thác FI trên HDB Han và cs. (1995) [21] - Khai thác 1 ngưỡng; Liu và cs. (1999) [32]; Tseng và cs. (2001) [40]; Vo và cs. (2012) [41] - GIT-tree. Khai thác 1 ngưỡng làm lu mờ các mục con ít xuất hiện. Khai thác nhiều ngưỡng theo Apriori quét CSDL nhiều lần; GIT-tree phải chèn trực tiếp các mục cha vào giao dịch của CSDL, làm tăng kích thước CSDL và tốn bộ nhớ.
Tiếp cận Bit-vector Louie & Liu (2004) [33]; Dong & Han (2007) [13]; Song và cs. [39] - Cấu trúc BitTable; Vo và cs. (2012) [43] - Cấu trúc DBV. BitTable dùng $(\lfloor \frac{

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

Luận án tập trung giải quyết 3 khoảng trống cốt lõi:

  1. Khắc phục sự lãng phí bộ nhớ và chi phí tính giao tidset của các cấu trúc bit-vector hiện có (DBV, BitTable) bằng cách xây dựng các cấu trúc mới loại bỏ hoàn toàn các đoạn 0 ở giữa và xử lý trên các đơn vị dữ liệu lớn (word 16-bit, multi-bit segment).
  2. Xây dựng bài toán và thuật toán khai thác $k$ nhóm tập mục phổ biến có thứ hạng cao nhất trên cơ sở dữ liệu số lượng ($\text{TRFWUI}_k$), kết hợp cấu trúc bảng động (DTab) và cấu trúc heap động (DHeap) để tối ưu hóa việc quản lý thứ hạng.
  3. Giải quyết triệt để bài toán khai thác FWUI trên cơ sở dữ liệu số lượng có sự phân cấp các mục (HQDB) mà không cần chèn các mục cha vào cơ sở dữ liệu, đồng thời phát triển cấu trúc EDBV để nâng cao tốc độ tính toán.

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

Các mô hình cơ sở dữ liệu và công thức tính toán

Luận án sử dụng các định nghĩa hình thức cho 5 mô hình cơ sở dữ liệu:

  • Cơ sở dữ liệu nhị phân (BDB): Bộ đôi $\langle T, I \rangle$, với tập giao dịch $T = {t_1, t_2, \dots, t_m}$ và tập mục $I = {i_1, i_2, \dots, i_n}$; $t_k \in {0, 1}^n$. Độ hỗ trợ: $\text{support}(X) = \frac{|{t \in T \mid X \subseteq t}|}{m} \times 100%$.
  • Cơ sở dữ liệu phân cấp (HDB): Bộ ba $\langle T, I, Tr \rangle$, trong đó $Tr$ là cây phân cấp thể hiện quan hệ trừu tượng hóa giữa các mục.
  • Cơ sở dữ liệu số lượng (QDB): Bộ ba $\langle T, I, W \rangle$, với $W = {w_1, w_2, \dots, w_n}$ là tập trọng số của các mục, giao dịch $t_k = {q_1, q_2, \dots, q_n}$ biểu diễn số lượng $q_i$ của mục $i_i$.
  • Cơ sở dữ liệu trọng số (WDB): Là biến thể của QDB với $q_i \in {0, 1}$.
  • Cơ sở dữ liệu số lượng có phân cấp (HQDB): Kết hợp giữa QDB và quan hệ cây phân cấp $Tr$.

Các độ đo trọng số và tính chất bao đóng giảm:

  1. Trọng số giao dịch ($tw$): $$tw(t_k) = \frac{\sum_{i_j \in t_k} w_j}{|t_k|}$$
  2. Độ hỗ trợ trọng số ($ws$): $$ws(X) = \frac{\sum_{t \in T(X)} tw(t)}{\sum_{t \in T} tw(t)}$$ với $T(X) = {t \in T \mid X \subseteq t}$. Tập $X$ là FWI nếu $ws(X) \ge minws$.
  3. Trọng số hữu ích giao dịch ($twu$): $$twu(t_k) = \frac{\sum_{i_j \in t_k} q_j \cdot w_j}{\sum_{i_j \in t_k} q_j}$$
  4. Độ hỗ trợ trọng số hữu ích ($wus$): $$wus(X) = \frac{\sum_{t \in T(X)} twu(t)}{\sum_{t \in T} twu(t)}$$ Tập $X$ là FWUI nếu $wus(X) \ge minwus$. Cả $ws$ và $wus$ đều thỏa mãn tính chất bao đóng giảm: Nếu $X \subseteq Y$ thì $ws(Y) \le ws(X)$ và $wus(Y) \le wus(X)$.

Phương pháp nghiên cứu

  • Phương pháp định tính: Phân tích cấu trúc dữ liệu và giải thuật hình thức; chứng minh các định lý, bổ đề toán học về tính chất bao đóng giảm, tính giao giữa các đoạn biểu diễn bit, và công thức ánh xạ chỉ số bit sang chỉ số giao dịch.
  • Phương pháp định lượng & Thực nghiệm: Xây dựng chương trình thử nghiệm, đo đạc thời gian thực thi (giây) và bộ nhớ tiêu thụ (MB) trên máy tính kiến trúc 64-bit; so sánh đối chuẩn trực tiếp giữa thuật toán đề xuất với các thuật toán hiện có trên 7 bộ dữ liệu chuẩn và thực tế.

Nguồn tư liệu và dữ liệu thực nghiệm

Luận án sử dụng các tập dữ liệu thử nghiệm chuẩn và dữ liệu thực tế bao gồm:

  1. RETAIL: Cơ sở dữ liệu giao dịch bán lẻ thưa.
  2. BMS_POS: Cơ sở dữ liệu điểm bán lẻ thương mại điện tử.
  3. SALE_FACT_1997, SALE_FACT_1997+1998, SALE_FACT_SYNC: Dữ liệu bán hàng thực tế có chứa cấu trúc phân cấp mặt hàng và số lượng/trọng số.
  4. CONNECT, ACCIDENTS: Cơ sở dữ liệu dày và bán nhân tạo.

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

Chương 1: Tổng quan về khai thác tập mục

Chương này trình bày toàn diện các khái niệm cơ sở và tổng quan tài liệu về bài toán khai thác tập mục:

  • Định nghĩa chi tiết các mô hình dữ liệu: CSDL nhị phân (BDB), CSDL có phân cấp (HDB), CSDL số lượng (QDB), CSDL trọng số (WDB).
  • Phân tích chi tiết các thuật toán khai thác FI trên CSDL ngang (Apriori, FP-Growth), CSDL dọc dựa trên IT-tree (Eclat), và cấu trúc diffset.
  • Hệ thống hóa các phương pháp khai thác FWI và FWUI trên QDB, chỉ rõ sự khác biệt giữa hai hướng tiếp cận: hướng tiếp cận dựa trên giá trị trung bình trọng số mục (Yun, Lan) và hướng tiếp cận dựa trên trọng số giao dịch $tw$/$twu$ (Tao, Khan, Vo).
  • Điểm luận bài toán khai thác $k$ nhóm tập mục phổ biến có thứ hạng cao nhất ($\text{TRFI}_k$) với các thuật toán VTK, NTK, iNTK.
  • Phân tích các tiếp cận khai thác trên CSDL có phân cấp các mục với một ngưỡng và nhiều ngưỡng hỗ trợ.
  • Tổng kết các kỹ thuật biểu diễn tidset bằng bit-vector (BitTable, DBV), phân tích nguyên nhân gây lãng phí không gian nhớ do các byte giá trị 0 ở giữa và độ phức tạp khi thao tác trên từng byte đơn lẻ.

Chương 2: Khai thác tập mục phổ biến trên cơ sở dữ liệu số lượng

Chương 2 tập trung vào việc đề xuất các cấu trúc dữ liệu và giải thuật mới để tối ưu hóa quá trình khai thác FWI, FWUI và $\text{TRFWUI}_k$ trên QDB:

1. Cấu trúc Interval Word Segment (IWS) và thuật toán khai thác FWI

  • Định nghĩa IWS: IWS của tập mục $X$ là tập các đoạn, mỗi đoạn gồm các word (2 byte = 16 bit) liên tiếp khác 0 trên bit-vector biểu diễn tidset của $X$. Một đoạn gồm hai thành phần: $\text{Start}$ (vị trí word đầu tiên) và $\text{Word list}$ (danh sách giá trị các word khác 0).
  • Công thức ánh xạ bit: Vị trí giao dịch $k$ của bit thứ $l$ trong word thứ $s_j$ được tính theo công thức: $$k = (s_j - 1) \times 16 + l$$
  • Thuật toán tính giao IWS: Giao hai IWS được thực hiện bằng cách chỉ tính giao giữa các đoạn có chỉ số word chồng lấn nhau thông qua phép toán AND bitwise (&), bỏ qua hoàn toàn các vùng word 0.
  • Thuật toán khai thác FWI dựa trên IWS-tree: Xây dựng cây tương tự WIT-tree nhưng mỗi nút lưu trữ IWS thay vì mảng tidset.
Bảng minh họa: Biểu diễn Bit-vector, DBV và IWS (Trích xuất từ Ví dụ 2.1 của luận án)
Dạng biểu diễn Cấu trúc lưu trữ Nhận xét
Bit-vector (32 byte) Dãy 32 byte: Byte 5=6, 6=9; Byte 10=1, 11=5, 12=1, 13=4, 14=6; Byte 24=1, 25=5, 26=4, 27=6; các byte còn lại = 0. Tốn trọn vẹn 32 byte bộ nhớ; chứa nhiều vùng byte 0.
DBV 5(6, 9, 0, 0, 0, 1, 5, 1, 4, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 4, 6) Cắt bỏ 4 byte 0 ở đầu và 5 byte 0 ở cuối; vẫn lưu 12 byte 0 ở giữa (độ dài 23 byte).
IWS {3(1545), 5(1, 1281, 1030), 12(1, 1284, 1536)} Loại bỏ hoàn toàn các word 0; chỉ lưu 3 đoạn với tổng cộng 7 word (14 byte dữ liệu + chỉ số đoạn).

2. Cấu trúc Multi Bit Segment (MBiS) và thuật toán khai thác FWUI

  • Mở rộng khái niệm phân đoạn xuống cấp độ chuỗi bit 1 liên tiếp (MBiS).
  • Đề xuất thuật toán xác định giao hai MBiS và thuật toán tính độ hỗ trợ trọng số hữu ích $wus$ trên cây MBiS-tree, giúp giảm tối đa bộ nhớ đệm và tăng tốc độ duyệt nhánh.

3. Bài toán và thuật toán khai thác $\text{TRFWUI}_k$

  • Luận án định nghĩa bài toán khai thác $k$ nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất trên QDB.
  • Cấu trúc DTab (Dynamic Table): Bảng động quản lý các nhóm tập mục theo thứ tự $wus$ giảm dần.
  • Cấu trúc DHeap (Dynamic Heap) & TR-tree: Cải tiến DTab bằng cấu trúc Max-Heap/Min-Heap động, cho phép chèn và cập nhật ngưỡng cắt tỉa tức thời với độ phức tạp $O(\log k)$. Thuật toán sử dụng DHeap giúp cắt tỉa nhanh các nhánh không thể lọt vào Top-$k$ trên cây TR-tree.
  • Kết quả thực nghiệm Chương 2: Thực nghiệm trên các CSDL RETAIL, BMS_POS, CONNECT, ACCIDENTS và chuỗi CSDL SALE_FACT cho thấy IWS và MBiS giảm từ 40% đến hơn 70% dung lượng bộ nhớ so với DBV và WIT-tree/MWIT-tree, đồng thời rút ngắn đáng kể thời gian chạy. Thuật toán khai thác $\text{TRFWUI}_k$ sử dụng DHeap vượt trội hơn phương pháp dùng DTab khi $k$ tăng.

Chương 3: Khai thác 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 mục

Chương 3 giải quyết bài toán phức tạp nhất của luận án: khai thác FWUI trên mô hình HQDB:

  • Mô hình bài toán: Gán trọng số $w$ cho các mục cha trên cây phân cấp $Tr$ dựa trên quan hệ kế thừa/trung bình từ các mục con; xác định tập mục hợp lệ không chứa quan hệ phụ thuộc cha-con trực tiếp ($\forall x, y \in X, x \text{ không là tổ tiên của } y$).
  • Hạn chế của phương pháp truyền thống: Việc thêm trực tiếp các mục cha vào các giao dịch của CSDL gốc làm tăng kích thước CSDL lên gấp nhiều lần (được chứng minh qua Bảng 1.13 của luận án: từ 11 mục tăng lên 21 mục trên 6 giao dịch).
  • Các cải tiến kỹ thuật trong Chương 3:
    1. Thuật toán tính trực tiếp tidset của nút cha từ tidset của nút con: Sử dụng phép toán OR bitwise trên các tidset con mà không cần sửa đổi CSDL gốc.
    2. Cấu trúc EDBV (Extended Dynamic Bit-vector): Mở rộng cấu trúc DBV kết hợp phân tách đoạn 2-byte, tối ưu hóa các phép toán AND và dịch bit.
    3. Thuật toán kiểm tra quan hệ cha-con: Kiểm tra nhanh ràng buộc xung đột phả hệ giữa các mục trong quá trình nối nút trên cây HIT-tree.
    4. Thuật toán khai thác nhanh FWUI trên HQDB: Kết hợp tính nhanh $wus$, cấu trúc EDBV và cây HIT-tree.
  • Kết quả thực nghiệm Chương 3: Thử nghiệm trên các tập dữ liệu có cấu trúc phân cấp SALE_FACT_1997, SALE_FACT_1997+1998 và SALE_FACT_SYNC chứng minh thuật toán cải tiến sử dụng EDBV giảm mạnh thời gian chạy và dung lượng bộ nhớ so với việc quét và mở rộng CSDL thông thường.

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

Đóng góp về mặt lý thuyết và giải thuật

  1. Đề xuất hai cấu trúc dữ liệu mới biểu diễn tidset (IWS và MBiS): Loại bỏ hoàn toàn các word/byte có giá trị 0 ở giữa mảng bit, khắc phục triệt để nhược điểm chiếm dụng bộ nhớ của BitTable và DBV; thiết lập công thức toán học ánh xạ chỉ số bit sang chỉ số giao dịch trên đơn vị word 16-bit.
  2. Định nghĩa và giải quyết bài toán $\text{TRFWUI}_k$ trên QDB: Lần đầu tiên đưa bài toán khai thác $k$ nhóm tập mục phổ biến có thứ hạng cao nhất lên CSDL số lượng; đề xuất giải thuật khai thác nhanh sử dụng cấu trúc bảng động DTab và heap động DHeap kết hợp cây TR-tree.
  3. Mô hình hóa và giải quyết toàn diện bài toán khai thác FWUI trên HQDB: Xây dựng cơ chế tính toán độ hỗ trợ hữu ích $wus$ và xác định tidset của các mục cha thông qua quan hệ phân cấp mà không cần nhân bản hay chèn mục cha vào CSDL vật lý; đề xuất cấu trúc EDBV và thuật toán xây dựng cây HIT-tree.

Đóng góp về mặt thực tiễn

  • Đưa ra giải pháp kỹ thuật có hiệu năng cao, giảm tải đáng kể áp lực bộ nhớ RAM và thời gian CPU khi khai thác các tập dữ liệu lớn và thưa.
  • Cung cấp công cụ phân tích mẫu dữ liệu đa chiều (số lượng, giá trị lợi ích, cấp độ danh mục sản phẩm) ứng dụng trực tiếp cho các hệ thống phân tích dữ liệu bán lẻ (OLAP, siêu thị), phân tích vi phạm giao thông và hỗ trợ chẩn đoán y tế.

Kiến nghị và đề xuất kỹ thuật

  • Khuyến nghị sử dụng biểu diễn tidset dựa trên đơn vị word 16-bit/large integer 64-bit thay vì thao tác trên từng byte đơn lẻ để tận dụng tập lệnh tính toán song song bitwise của các kiến trúc vi xử lý hiện đại.
  • Ứng dụng mô hình DHeap trong các bài toán khai thác Top-$k$ nhằm duy trì ngưỡng động một cách tối ưu, loại bỏ sớm các nhánh không tiềm năng trong cây tìm kiếm.

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

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

  • Luận án tập trung chủ yếu vào mô hình dữ liệu tĩnh được nạp vào bộ nhớ trong (in-memory computing) theo định dạng dọc; chưa mở rộng đánh giá trên mô hình dữ liệu dòng (data stream) hoặc môi trường tính toán phân tán.
  • Các cấu trúc IWS và MBiS được tối ưu hóa đặc biệt cho CSDL thưa; đối với các CSDL cực dày (dense databases), mức độ tiết kiệm bộ nhớ so với cấu trúc diffset chưa có sự cách biệt vượt trội.

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

Căn cứ theo phần "Kết luận và Hướng phát triển" của văn bản luận án:

  1. Nghiên cứu mở rộng cấu trúc IWS và MBiS để lưu trữ và xử lý với các số nguyên lớn (Large Integer - 8 byte / 64 bit) nhằm khai thác tối đa sức mạnh của hệ thống máy tính 64-bit.
  2. Nghiên cứu áp dụng các cấu trúc và thuật toán đề xuất vào bài toán khai thác tập mục đóng (closed itemsets) và tập mục tối đại (maximal itemsets) trên CSDL số lượng có phân cấp.
  3. Nghiên cứu triển khai các giải thuật trên các nền tảng tính toán song song, phân tán (như MapReduce/Hadoop hoặc Spark) để xử lý dữ liệu quy mô cực 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 cao cho các nhóm đối tượng:

  • Nghiên cứu sinh và học viên cao học ngành Khoa học máy tính / Công nghệ thông tin: Tham khảo phương pháp luận thiết kế cấu trúc dữ liệu nhị phân nâng cao, kỹ thuật tối ưu hóa bitwise và phương pháp mở rộng các thuật toán khai thác cây (IT-tree, WIT-tree, MWIT-tree).
  • Giảng viên và nhà nghiên cứu trong lĩnh vực Khai phá dữ liệu (Data Mining): Sử dụng các mô hình định nghĩa hình thức chuẩn xác về $tw, ws, twu, wus$ và bài toán HQDB làm học liệu giảng dạy và phát triển các hướng nghiên cứu chuyên sâu.
  • Kỹ sư phát triển phần mềm và chuyên gia phân tích dữ liệu kinh doanh (BI): Ứng dụng các thuật toán IWS, DHeap và HIT-tree để xây dựng các module gợi ý mặt hàng (Recommender Systems), tối ưu hóa kho bãi và khai thác luật kết hợp đa cấp trong các hệ thống thương mại điện tử và bán lẻ.

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

1. Cấu trúc IWS (Interval Word Segment) cải tiến điểm yếu nào của cấu trúc DBV (Dynamic Bit-vector)?

Cấu trúc DBV trước đây chỉ loại bỏ các byte 0 ở hai đầu dãy bit-vector nhưng vẫn giữ nguyên toàn bộ các byte 0 nằm ở giữa, gây lãng phí bộ nhớ lớn trên các CSDL thưa. IWS chia bit-vector thành các đoạn word (2 byte = 16 bit) liên tiếp khác 0 và loại bỏ hoàn toàn các word có giá trị 0 ở giữa, chỉ lưu vị trí bắt đầu ($\text{Start}$) và mảng giá trị word ($\text{Word list}$), giúp tiết kiệm đáng kể bộ nhớ và đẩy nhanh phép toán giao AND bitwise.

2. Sự khác nhau căn bản giữa độ hỗ trợ trọng số ($ws$) và độ hỗ trợ trọng số hữu ích ($wus$) là gì?

  • Độ hỗ trợ trọng số ($ws$): Áp dụng trên CSDL trọng số (WDB), trong đó mỗi mục chỉ có một trọng số cố định $w_i$, số lượng xuất hiện trong giao dịch là nhị phân ($0$ hoặc $1$). $ws$ dựa trên trọng số giao dịch $tw(t_k)$ là trung bình cộng trọng số các mục trong giao dịch.
  • Độ hỗ trợ trọng số hữu ích ($wus$): Áp dụng trên CSDL số lượng (QDB), xét đồng thời cả trọng số $w_i$ và số lượng mua $q_i$ của từng mục trong mỗi giao dịch. $wus$ dựa trên trọng số hữu ích giao dịch $twu(t_k)$ tính bằng tổng tích số lượng và trọng số chia cho tổng số lượng mục trong giao dịch đó.

3. Tại sao trong bài toán khai thác $\text{TRFWUI}_k$, cấu trúc DHeap lại cho hiệu năng tốt hơn cấu trúc DTab?

Cấu trúc DTab là bảng động đòi hỏi phải duyệt và cập nhật danh sách tuyến tính khi bổ sung ứng viên mới, dẫn đến chi phí thời gian cao khi số lượng nhóm $k$ tăng. DHeap tổ chức dữ liệu theo cấu trúc Heap động, cho phép xác định phần tử có $wus$ nhỏ nhất trong Top-$k$ với thời gian $O(1)$ và cập nhật chèn phần tử mới với độ phức tạp $O(\log k)$, giúp nâng ngưỡng cắt tỉa nhánh nhanh chóng trên cây TR-tree.

4. Thuật toán khai thác FWUI trên HQDB của luận án giải quyết vấn đề bùng nổ kích thước CSDL như thế nào?

Các tiếp cận truyền thống phải quét CSDL và thêm tường minh tất cả các mục cha trên cây phân cấp vào từng giao dịch chứa mục con, làm tăng gấp đôi số lượng mục và dung lượng dữ liệu. Luận án đề xuất thuật toán tính trực tiếp tidset của mục cha thông qua phép hợp (OR bitwise) tidset của các mục con trên cây phân cấp kết hợp cấu trúc EDBV, giữ nguyên CSDL gốc mà vẫn khai thác đầy đủ các tập mục cha-con hợp lệ.

5. CSDL thực nghiệm SALE_FACT_1997 và SALE_FACT_SYNC có đặc trưng gì phù hợp với luận án?

Đây là các bộ dữ liệu bán hàng thực tế chứa đầy đủ thông tin về số lượng mặt hàng ($q_i$), giá trị/trọng số mặt hàng ($w_i$) và cây phân loại danh mục sản phẩm nhiều mức (ví dụ: máy tính $\rightarrow$ máy tính bàn / máy tính xách tay; máy in $\rightarrow$ máy in kim / máy in phun / máy in laser). Do đó, chúng phản ánh đầy đủ các ràng buộc của mô hình CSDL số lượng có phân cấp (HQDB) mà luận án nghiên cứu.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Duy Hàm đã giải quyết một cách có hệ thống bài toán khai thác tập mục phổ biến trên các mô hình cơ sở dữ liệu nâng cao thông qua việc đề xuất các cấu trúc dữ liệu dạng bit-vector cải tiến (IWS, MBiS, EDBV) và các giải thuật khai thác hiệu năng cao (IWS-tree, DHeap trên TR-tree, HIT-tree). Các đóng góp của công trình bao gồm việc khắc phục triệt để sự lãng phí không gian nhớ của các kỹ thuật biểu diễn tidset truyền thống, lần đầu tiên định nghĩa và giải quyết bài toán $\text{TRFWUI}_k$ trên cơ sở dữ liệu số lượng, cùng giải pháp khai thác cơ sở dữ liệu số lượng có phân cấp mà không làm tăng dung lượng lưu trữ vật lý. Kết quả thực nghiệm trên các tập dữ liệu chuẩn và thực tế đã chứng minh tính đúng đắn và hiệu quả vượt trội của các thuật toán đề xuất về cả thời gian thực thi lẫn dung lượng bộ nhớ sử dụng.