Tổng quan luận án

Trong lĩnh vực khai phá dữ liệu (Data Mining), khai phá tập mục thường xuyên và khai phá mẫu dãy tuần tự (Sequential Pattern Mining) là những hướng nghiên cứu nền tảng được đề xuất lần đầu bởi Agrawal và Srikant (1994, 1995). Mục tiêu của các phương pháp này là phát hiện các mẫu hành vi, sự kiện xuất hiện phổ biến trong cơ sở dữ liệu giao dịch hoặc cơ sở dữ liệu chuỗi. Tuy nhiên, các kỹ thuật khai phá mẫu dãy truyền thống tồn tại ba hạn chế lớn khi áp dụng vào thực tiễn:

  1. Bỏ qua khoảng cách thời gian giữa các sự kiện trong chuỗi: Trong các bài toán thực tế như phân tích hành vi mua sắm, theo dõi luồng nhấp chuột (clickstream), tin sinh học hay nhật ký mạng, khoảng cách thời gian giữa các giao dịch mang ý nghĩa quyết định (ví dụ: giao dịch mua hàng lặp lại sau 1 ngày khác biệt về bản chất so với giao dịch lặp lại sau 1 năm).
  2. Giả định mọi mục dữ liệu đều có độ quan trọng ngang nhau: Trên thực tế, mỗi mặt hàng có giá trị, tỉ trọng hoặc mức độ ưu tiên khác nhau (ví dụ: máy in có giá trị cao nhưng tần suất mua thấp, trong khi giấy in có giá trị thấp nhưng tần suất mua cao).
  3. Bỏ qua giá trị số lượng định lượng của các mục trong từng lần xuất hiện: Các mô hình truyền thống chỉ ghi nhận sự xuất hiện nhị phân (có/không), chưa tính toán được khối lượng hàng hóa mua và mức lợi nhuận thực tế (lợi ích/utility) mang lại.
  4. Khó khăn trong việc thiết lập ngưỡng hỗ trợ tối thiểu ($minsup$ hoặc $wminsup$): Người dùng thường thiếu kiến thức chuyên sâu về cơ sở dữ liệu để chọn ngưỡng phù hợp, dẫn đến tình trạng sinh ra quá nhiều mẫu thừa hoặc bỏ sót các mẫu quan trọng.

Khoảng trống nghiên cứu mà luận án xác định bao gồm:

  • Chưa có nhiều công trình nghiên cứu giải quyết bài toán khai phá top-$k$ mẫu dãy thường xuyên có trọng số trong cơ sở dữ liệu dãy có tích hợp khoảng cách thời gian ($iSDB$), nơi kết hợp đồng thời cả trọng số chuẩn hóa của từng mục, các ràng buộc thời gian nghiêm ngặt và cơ chế tự động tìm $k$ mẫu có giá trị cao nhất mà không cần người dùng thiết lập ngưỡng hỗ trợ cố định.
  • Thiếu các giải thuật hiệu quả để khai phá mẫu dãy lợi ích cao trong cơ sở dữ liệu dãy định lượng có khoảng cách thời gian ($QiSDB$), đặc biệt là các thuật toán tiếp cận một pha (1-phase) sử dụng cấu trúc bảng lợi ích nhằm khắc phục hạn chế về bộ nhớ và thời gian của các giải thuật hai pha (2-phase) truyền thống.

Mục tiêu nghiên cứu của luận án: Đề xuất các giải pháp, mô hình toán học và thuật toán hiệu quả nhằm khai phá các mẫu dãy có trọng số, có tính đến khoảng cách thời gian trong hai loại cơ sở dữ liệu: cơ sở dữ liệu dãy có khoảng cách thời gian ($iSDB$) và cơ sở dữ liệu dãy định lượng có khoảng cách thời gian ($QiSDB$). Cụ thể:

  1. Mục tiêu 1: Nghiên cứu, phát triển thuật toán khai phá top-$k$ mẫu dãy thường xuyên trọng số với khoảng cách thời gian trong cơ sở dữ liệu $iSDB$.
  2. Mục tiêu 2: Nghiên cứu, phát triển các thuật toán khai phá mẫu dãy thường xuyên lợi ích cao có khoảng cách thời gian trong cơ sở dữ liệu định lượng $QiSDB$ (bao gồm cả phương pháp hai pha và phương pháp một pha).
  3. Mục tiêu 3: Chứng minh toán học về tính đúng đắn, tính đầy đủ, phân tích độ phức tạp tính toán và tiến hành thực nghiệm đánh giá hiệu năng trên các bộ dữ liệu chuẩn.

Đối tượng nghiên cứu:

  • Dữ liệu có giá trị trọng số trong cơ sở dữ liệu dãy có khoảng cách thời gian ($iSDB$).
  • Dữ liệu có giá trị trọng số và giá trị định lượng trong cơ sở dữ liệu dãy định lượng có khoảng cách thời gian ($QiSDB$).
  • Các cấu trúc dữ liệu, kỹ thuật tỉa nhánh không gian tìm kiếm và các thuật toán khai phá mẫu dãy có trọng số, có ràng buộc khoảng cách thời gian và mẫu dãy lợi ích cao.

Phạm vi nghiên cứu:

  • Tập trung vào các mẫu dãy tuần tự, trọng số của các mục trong dãy, 04 ràng buộc khoảng cách thời gian ($C_1, C_2, C_3, C_4$), giá trị định lượng (số lượng mua) và giá trị lợi ích.
  • Nghiên cứu không gian thuật toán phát triển từ phương pháp tăng trưởng mẫu dãy (Pattern Growth / PrefixSpan), kỹ thuật biểu diễn dọc và cấu trúc bảng lợi ích.
  • Thực nghiệm kiểm chứng trên các tập dữ liệu chuẩn từ kho dữ liệu UCI (UC Irvine Machine Learning Repository) và các tập dữ liệu mô phỏng.

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

Luận án đã hệ thống hóa và phân loại các công trình nghiên cứu liên quan theo 04 nhóm hướng tiếp cận chính:

STT Nhóm hướng nghiên cứu Các công trình, tác giả tiêu biểu Thuật toán tiêu biểu
I Khai phá mẫu dãy thường xuyên
1.1 Phương pháp duyệt dạng Apriori (chiều rộng) R. Agrawal, R. Srikant (1995, 1996) AprioriAll, GSP
1.2 Phương pháp biểu diễn dọc (chiều sâu) M. Zaki (2001); J. Ayres et al. (2002); P. Fournier-Viger et al. (2014) SPADE, SPAM, Lapin-Spam, CM-Spam, CM-Spade
1.3 Phương pháp tăng trưởng mẫu dãy J. Pei, J. Han et al. (2000, 2001, 2004) FreeSpan, PrefixSpan
II Khai phá mẫu dãy có trọng số U. Yun et al. (2008); W. Wei et al.; F. Tao; H. Li et al. (2008) MWSP, WSpan, WSPM, WCSpan
III Khai phá mẫu dãy lợi ích cao (HUSP) C. F. Ahmed et al. (2010); J. Z. Lan et al. (2012); J. Yin et al. (2012); O. C. Alkan et al. (2016); T. Truong-Chi & P. Fournier-Viger (2019); L. Feremans et al. (2019) UL, US, USpan, PHUS, HuspExt, HUS-Span, HUSPM, QCSP
IV Khai phá mẫu dãy với khoảng cách thời gian M. Zaki (2000); J. Pei et al. (2002); Y. L. Chen et al. (2003, 2005); Y. Hirate & H. Yamana (2006); S. J. Yen et al. (2013); C. Y. Chang (2011); Trần Huy Dương et al. (2015) cSpade, Prefix-growth, I-Apriori, I-PrefixSpan, FTI-Apriori, FTI-PrefixSpan, Thuật toán Hirate & Yamana, TGSP, TiWS, WIPrefixSpan
V Khai phá top-k và tiếp cận mờ P. Fournier-Viger et al. (2013); T. V. Phương et al. (2018) TKS, FSPFTIM

Vị trí và khoảng trống luận án lựa chọn giải quyết:

  • Kế thừa và phát triển từ thuật toán TKS (Fournier-Viger et al., 2013) về cơ chế khai phá top-$k$ và thuật toán WIPrefixSpan (Dương et al., 2015) về khai phá mẫu dãy trọng số có khoảng cách thời gian, luận án giải quyết bài toán khai phá top-$k$ mẫu dãy thường xuyên trọng số với khoảng cách thời gian mà không cần tham số $wminsup$, tích hợp đầy đủ 04 ràng buộc thời gian.
  • Kế thừa các nghiên cứu về HUSP (như UL, US, USpan, HUS-Span, HUSPM) và bài toán thời gian (Hirate & Yamana, Chen et al.), luận án giải quyết trọn vẹn bài toán khai phá mẫu dãy lợi ích cao trong cơ sở dữ liệu định lượng có khoảng cách thời gian ($QiSDB$) thông qua hai thuật toán mới: UIPrefixSpan (tiếp cận 2 pha) và HUISP (tiếp cận 1 pha dùng bảng lợi ích).

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

Cơ sở lý thuyết và các khái niệm hình thức

  1. Cơ sở dữ liệu dãy có trọng số ($SDB$):

    • Tập các mục $I = {i_1, i_2, \dots, i_n}$, mỗi mục $i_j \in I$ được gán một trọng số $w_j \in (0, 1]$.
    • Một tập mục $s_j \subseteq I$ là một tập con khác rỗng. Dãy $S = \langle (s_1), (s_2), \dots, (s_m) \rangle$.
    • Kích thước $|S|$ là tổng số phần tử $s_j$; Độ dài $l(S)$ là tổng số mục $i_j$ xuất hiện trong $S$.
    • Trọng số chuẩn hóa của dãy $\alpha$ có độ dài $k$: $$NW(\alpha) = \frac{1}{k} \sum_{i_j \in \alpha} w_j$$
    • Độ hỗ trợ có trọng số chuẩn hóa của dãy $\alpha$: $$NWsupport(\alpha) = NW(\alpha) \times sup(\alpha) = \left( \frac{1}{k} \sum_{i_j \in \alpha} w_j \right) \times sup(\alpha)$$
    • Mẫu dãy $\alpha$ là thường xuyên trọng số nếu $NWsupport(\alpha) \ge wminsup$. Do $NWsupport$ không có tính phản đơn điệu (Anti-monotonicity), một dãy con không thỏa ngưỡng vẫn có thể kết hợp với các mục có trọng số cao hơn để tạo thành dãy dài hơn thỏa ngưỡng.

  2. Cơ sở dữ liệu dãy có khoảng cách thời gian ($iSDB$):

    • Mỗi dãy $S$ có dạng $S = \langle (t_{1,1}, s_1), (t_{1,2}, s_2), \dots, (t_{1,m}, s_m) \rangle$, trong đó $t_{1,j}$ là khoảng cách thời gian từ phần tử đầu tiên $s_1$ đến $s_j$.
    • 04 ràng buộc khoảng cách thời gian:
      • $C_1 = min_time_interval$: Khoảng cách tối thiểu giữa 2 phần tử liền kề ($t_{i, i+1} \ge C_1$).
      • $C_2 = max_time_interval$: Khoảng cách tối đa giữa 2 phần tử liền kề ($t_{i, i+1} \le C_2$).
      • $C_3 = min_whole_interval$: Khoảng cách tối thiểu giữa phần tử đầu và phần tử cuối ($t_{1, m} \ge C_3$).
      • $C_4 = max_whole_interval$: Khoảng cách tối đa giữa phần tử đầu và phần tử cuối ($t_{1, m} \le C_4$).
      • Đặc tính: $C_1, C_2, C_4$ là các ràng buộc phản đơn điệu; $C_3$ là ràng buộc đơn điệu. Điều kiện logic: $C_1 \le C_2$, $C_3 \le C_4$, $C_1 \le C_4$, $C_2 \le C_4$.
    • Chiến lược cắt tỉa bảo toàn tính phản đơn điệu: Dãy ứng viên thỏa mãn: $$sup(\alpha) \times MaxW \ge wminsup \quad \text{và thỏa mãn các ràng buộc } C_1, C_2, C_3, C_4$$ với $MaxW = \max_{i_j \in I} w_j$.

  3. Cơ sở dữ liệu dãy định lượng có khoảng cách thời gian ($QiSDB$):

    • Mở rộng $iSDB$ bằng cách bổ sung giá trị số lượng mua (internal utility - $q(i, s)$) của mỗi mục trong mỗi giao dịch và giá trị lợi nhuận biên (external utility - $p(i)$ hay trọng số) của mỗi mục.
    • Cấu trúc tiền tố (Prefix), hậu tố (Postfix), cơ sở dữ liệu chiếu ($SDB|\alpha$, $iSDB|\alpha$, $QiSDB|\alpha$) và các bảng lợi ích (Utility Table) được sử dụng để quản lý không gian tìm kiếm.

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

  • Phương pháp nghiên cứu lý thuyết:
    • Xây dựng các mô hình toán học hình thức hóa bài toán.
    • Thiết kế các thuật toán dựa trên nền tảng kỹ thuật tăng trưởng mẫu dãy (Prefix-projected Sequential Pattern Mining).
    • Chứng minh các định lý, mệnh đề về tính đúng đắn (Correctness - không sinh ra mẫu sai) và tính đầy đủ (Completeness - không bỏ sót mẫu thỏa mãn).
    • Đánh giá độ phức tạp tính toán về thời gian chạy ($Time\ Complexity$) và không gian bộ nhớ ($Space\ Complexity$).
  • Phương pháp nghiên cứu thực nghiệm:
    • Cài đặt các thuật toán bằng ngôn ngữ lập trình.
    • Sử dụng các tập dữ liệu thực nghiệm chuẩn từ kho dữ liệu UCI (như các tập dữ liệu giao dịch, chuỗi ký tự, web clickstream).
    • Đo đạc định lượng các chỉ số: thời gian thực thi (giây), dung lượng bộ nhớ tiêu thụ (MB), số lượng mẫu ứng viên sinh ra và số lượng mẫu kết quả thực tế khi thay đổi các tham số $k$, $minsup$, $wminsup$, ngưỡng lợi ích tối thiểu ($min_utility$) và các giá trị ràng buộc thời gian $C_1, C_2, C_3, C_4$.

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

Chương 1: Tổng quan khai phá mẫu dãy có trọng số trong cơ sở dữ liệu dãy

Chương 1 thiết lập nền tảng lý thuyết và tổng quan toàn diện về các phương pháp khai phá mẫu dãy tuần tự, phân tích ưu nhược điểm của từng nhóm tiếp cận:

  • Nhóm thuật toán tìm kiếm theo chiều rộng (như AprioriAll, GSP): Sử dụng phương pháp sinh ứng viên cấp độ $k$ từ cấp độ $k-1$ và duyệt CSDL nhiều lần. Hạn chế là không gian tìm kiếm ứng viên bùng nổ (lên tới $2^m$ với dãy độ dài $m$), tiêu tốn bộ nhớ lớn để duy trì tập ứng viên và tốn chi phí I/O khi kiểm tra các mẫu không tồn tại.
  • Nhóm thuật toán tìm kiếm theo chiều sâu dùng định dạng dọc (như SPADE, SPAM, CM-Spam): Sử dụng cấu trúc danh sách định danh (IDList) hoặc mảng bit (Bitmaps) để chuyển đổi CSDL ngang thành CSDL dọc. Duyệt CSDL một lần duy nhất và tính độ hỗ trợ bằng các phép giao tập hợp, cải thiện tốc độ nhưng tiêu tốn bộ nhớ lớn khi CSDL dày đặc.
  • Nhóm thuật toán tăng trưởng mẫu dãy (như FreeSpan, PrefixSpan): Khai phá theo chiều sâu đệ quy bằng cách xây dựng các CSDL chiếu (projected database) theo tiền tố. Tránh hoàn toàn việc sinh ứng viên không tồn tại trong CSDL.
  • Điểm luận chi tiết các mở rộng: Khai phá mẫu dãy có trọng số ($MWSP$, $WSpan$, $WSPM$), khai phá mẫu dãy có khoảng cách thời gian ($cSpade$, $I-PrefixSpan$, $TGSP$, $TiWS$, thuật toán Hirate & Yamana, $WIPrefixSpan$), khai phá top-$k$ mẫu dãy ($TKS$) và khai phá mẫu dãy lợi ích cao ($UL$, $US$, $USpan$, $HUS-Span$, $HUSPM$, $QCSP$).

Chương 1 cũng minh họa chi tiết các khái niệm thông qua các bảng dữ liệu chuẩn:

  • Bảng CSDL dãy $SDB$ mẫu gồm 6 chuỗi giao dịch ($S_1$ đến $S_6$) với 7 mặt hàng $I = {a, b, c, d, e, f, g}$.
  • Bảng trọng số $W$: $w(a)=0.3, w(b)=0.2, w(c)=0.1, w(d)=0.6, w(e)=0.5, w(f)=0.2, w(g)=0.8$.
  • Bảng CSDL dãy có khoảng cách thời gian $iSDB$ và CSDL định lượng $QiSDB$.

Chương 2: Khai phá mẫu dãy có trọng số trong cơ sở dữ liệu dãy có khoảng cách thời gian

Chương 2 tập trung giải quyết bài toán khai phá top-$k$ mẫu dãy thường xuyên trọng số có khoảng cách thời gian trên $iSDB$:

  • Bài toán đặt ra: Cho CSDL $iSDB$, bảng trọng số $W$, các ràng buộc thời gian $C_1, C_2, C_3, C_4$ và số nguyên dương $k$. Cần tìm tập $\mathcal{T}$ gồm đúng $k$ mẫu dãy có giá trị $NWsupport$ lớn nhất thỏa mãn 04 ràng buộc thời gian mà không cần yêu cầu người dùng nhập ngưỡng $wminsup$.
  • Ý tưởng và cấu trúc thuật toán TopKWFP (Top-$k$ Weighted Sequential Pattern Mining with Item Interval):
    • Khởi tạo ngưỡng hỗ trợ động ban đầu $\varepsilon = 0$ và cấu trúc hàng đợi ưu tiên / danh sách $L$ chứa top-$k$ mẫu.
    • Sử dụng phương pháp tăng trưởng mẫu dãy dựa trên PrefixSpan kết hợp điều kiện tỉa nhánh an toàn: Một mẫu dãy ứng viên $\alpha$ chỉ được tiếp tục mở rộng nếu $sup(\alpha) \times MaxW \ge \varepsilon$ và thỏa mãn các ràng buộc phản đơn điệu ($C_1, C_2, C_4$).
    • Khi danh sách $L$ chưa đủ $k$ phần tử, mọi mẫu thỏa mãn được đưa vào $L$. Khi $L$ đã đủ $k$ phần tử, ngưỡng $\varepsilon$ được nâng lên bằng giá trị $NWsupport$ nhỏ nhất trong $L$ ($\varepsilon = \min {NWsupport(t) \mid t \in L}$).
    • Ngưỡng $\varepsilon$ tăng đơn điệu trong suốt quá trình đệ quy giúp không gian tìm kiếm được thu hẹp liên tục.
  • Phân tích thuật toán:
    • Chứng minh tính đúng đắn: Mọi mẫu dãy xuất ra từ TopKWFP đều thỏa mãn đầy đủ 04 ràng buộc $C_1, C_2, C_3, C_4$ và có $NWsupport \ge \varepsilon$.
    • Chứng minh tính đầy đủ: Không có mẫu dãy nào trong CSDL có $NWsupport$ thuộc top-$k$ mà bị bỏ sót, nhờ cận trên $sup(\alpha) \times MaxW \ge NWsupport(\alpha')$ với mọi phần mở rộng $\alpha'$ của $\alpha$.
  • Kết quả thực nghiệm:
    • Đánh giá trên các bộ dữ liệu chuẩn từ UCI với các kích thước khác nhau.
    • Khảo sát sự ảnh hưởng của tham số $k$: Khi $k$ tăng, thời gian chạy và bộ nhớ sử dụng tăng tuyến tính hoặc cận tuyến tính, số lượng ứng viên được kiểm soát chặt chẽ.
    • Đánh giá chiến lược tối ưu: Chiến lược nâng ngưỡng động $\varepsilon$ và tỉa bằng $MaxW$ giúp giảm đáng kể số lượng ứng viên sinh ra so với việc duyệt vét cạn.
    • So sánh đối sánh với thuật toán WIPrefixSpan: TopKWFP loại bỏ hoàn toàn việc phải thử nghiệm - sai nhiều lần để dò tìm ngưỡng $wminsup$, đạt hiệu năng thực thi tương đương hoặc vượt trội trong các điều kiện kiểm thử.

Chương 3: Khai phá mẫu dãy lợi ích cao trong cơ sở dữ liệu dãy có khoảng cách thời gian

Chương 3 đề xuất hai thuật toán giải quyết bài toán khai phá mẫu dãy lợi ích cao trong cơ sở dữ liệu định lượng có khoảng cách thời gian ($QiSDB$):

  1. Thuật toán UIPrefixSpan (High Utility Sequential Patterns with Time Interval - Tiếp cận 2 pha):

    • Pao 1 (Sinh ứng viên tiềm năng): Mở rộng cấu trúc cơ sở dữ liệu chiếu PrefixSpan trên $QiSDB$, sử dụng độ đo giới hạn trên Sequence-Weighted Utility ($SWU$) kết hợp với cận trên trọng số và kiểm tra các ràng buộc thời gian $C_1, C_2, C_4$ để sinh tập mẫu dãy có lợi ích cao tiềm năng (HTSP - High Utility Candidate Sequential Patterns).
    • Pha 2 (Xác thực lợi ích thực tế): Duyệt lại CSDL chiếu hoặc CSDL gốc để tính toán chính xác lợi ích thực tế của từng mẫu trong HTSP, kiểm tra ràng buộc đơn điệu $C_3$, loại bỏ các mẫu không đạt ngưỡng lợi ích tối thiểu $min_utility$.
    • Đánh giá: UIPrefixSpan lọc bỏ được không gian tìm kiếm lớn so với phương pháp vét cạn, tuy nhiên pha 2 đòi hỏi chi phí tính toán lại và việc tạo CSDL chiếu nhiều lần gây tốn bộ nhớ.

  2. Thuật toán HUISP (High Utility Item Interval Sequential Pattern - Tiếp cận 1 pha):

    • Cơ chế hoạt động: Đề xuất cấu trúc bảng lợi ích (Utility Table / Utility Matrix) kết hợp thông tin mốc thời gian của từng mục trong mỗi chuỗi giao dịch.
    • Sử dụng các cận trên chặt hơn để ước lượng lợi ích tối đa của các phần mở rộng mà không cần thực hiện phép chiếu CSDL vật lý đệ quy.
    • Khai phá trực tiếp các mẫu dãy lợi ích cao trong một pha duy nhất, loại bỏ hoàn toàn giai đoạn sinh ứng viên dư thừa của pha 2.
  • Phân tích so sánh và thử nghiệm:
    • Thử nghiệm trên các tập dữ liệu chuẩn UCI với 1000 mục, phân phối giá trị lợi nhuận khác nhau.
    • Thời gian thực thi: HUISP nhanh hơn rõ rệt so với UIPrefixSpan do không phải duyệt lại CSDL để tính toán lợi ích thực tế và không tốn thời gian sao chép CSDL chiếu.
    • Bộ nhớ sử dụng: HUISP duy trì mức tiêu thụ bộ nhớ ổn định hơn nhờ cấu trúc bảng chỉ mục và bảng lợi ích gọn nhẹ.
    • Số lượng ứng viên: HUISP giảm thiểu số lượng mẫu ứng viên trung gian so với UIPrefixSpan, trong khi tập kết quả mẫu dãy lợi ích cao cuối cùng của cả hai thuật toán là hoàn toàn trùng khớp (đảm bảo tính chính xác và đầy đủ).

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

Đóng góp về mặt lý luận và khoa học

  1. Đề xuất thuật toán TopKWFP: Đóng góp giải thuật khai phá top-$k$ mẫu dãy thường xuyên trọng số có khoảng cách thời gian đầu tiên trên cơ sở dữ liệu $iSDB$. Thuật toán kết hợp hài hòa giữa kỹ thuật tăng trưởng mẫu dãy (PrefixSpan), chiến lược nâng ngưỡng hỗ trợ động $\varepsilon$ và cận trên $MaxW$ để khắc phục triệt để tính phi phản đơn điệu của độ đo trọng số chuẩn hóa ($NWsupport$). Kết quả công bố tại công trình [CT1].
  2. Đề xuất thuật toán UIPrefixSpan: Đóng góp mô hình khai phá mẫu dãy lợi ích cao hai pha trên cơ sở dữ liệu định lượng có khoảng cách thời gian ($QiSDB$), tích hợp thành công 04 ràng buộc thời gian vào không gian tăng trưởng mẫu dãy lợi ích cao. Kết quả công bố tại các công trình [CT2], [CT3].
  3. Đề xuất thuật toán HUISP: Đóng góp giải thuật một pha tiên tiến sử dụng cấu trúc bảng lợi ích và bảng chỉ mục thời gian, giải quyết triệt để bài toán khai phá mẫu dãy lợi ích cao trên $QiSDB$ mà không cần sinh ứng viên trung gian hay duyệt lại CSDL nhiều lần. Kết quả công bố tại các công trình [CT4], [CT5].
  4. Hoàn thiện hệ thống chứng minh hình thức: Cung cấp đầy đủ các chứng minh toán học về tính đúng đắn, tính đầy đủ và phân tích độ phức tạp thời gian/không gian của các thuật toán đề xuất.

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

  • Cung cấp các công cụ thuật toán cho phép phân tích chính xác hành vi người tiêu dùng trong thương mại điện tử và bán lẻ, kết hợp đồng thời ba yếu tố then chốt: thứ tự chuỗi sự kiện, chu kỳ/khoảng cách thời gian mua sắm, và giá trị lợi nhuận biên của từng món hàng.
  • Hỗ trợ các nhà quản trị doanh nghiệp xây dựng chiến lược tiếp thị liên kết, đồng quảng cáo, định giá sản phẩm và quản lý chuỗi cung ứng dựa trên các mẫu chuỗi có giá trị kinh tế cao nhất.

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 xử lý trên các cơ sở dữ liệu tĩnh; chưa tối ưu hóa cho môi trường dòng dữ liệu liên tục (Data Streams) nơi dữ liệu cập nhật theo thời gian thực với tốc độ cao.
  • Thuật toán UIPrefixSpan vẫn chịu chi phí tính toán và bộ nhớ lớn khi CSDL có kích thước lớn và ngưỡng lợi ích thấp do phải duy trì các CSDL chiếu.
  • Các khoảng cách thời gian và giá trị định lượng hiện được xử lý dưới dạng các giá trị rời rạc, chưa tích hợp các tập mờ (Fuzzy Logic) để mô hình hóa các khoảng thời gian mờ trong ngôn ngữ tự nhiên.

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

  1. Mở rộng và phát triển các thuật toán TopKWFP, HUISP trên nền tảng tính toán phân tán và xử lý dữ liệu lớn (như Apache Spark, Hadoop) để xử lý các kho dữ liệu quy mô hàng tỷ bản ghi.
  2. Nghiên cứu khai phá mẫu dãy có trọng số và mẫu dãy lợi ích cao với khoảng cách thời gian trên môi trường dòng dữ liệu (Data Streams).
  3. Tích hợp lý thuyết tập mờ (Fuzzy Sets) để phát hiện các mẫu dãy có khoảng cách thời gian mờ và giá trị định lượng mờ.
  4. Phát triển các giải thuật bảo vệ thông tin nhạy cảm (Privacy-Preserving Utility Mining) nhằm ẩn các mẫu dãy lợi ích cao trong CSDL định lượng có khoảng cách thời gian.

Giá trị tham khảo

  • Đối với 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 máy tính: Luận án là tài liệu tham khảo chi tiết về kỹ thuật thiết kế thuật toán khai phá mẫu dãy nâng cao, phương pháp xử lý các hàm độ đo không thỏa mãn tính phản đơn điệu, và kỹ thuật tích hợp ràng buộc thời gian vào không gian tăng trưởng mẫu dãy.
  • Đối với các chuyên gia phân tích dữ liệu (Data Scientists/Engineers) và nhà quản lý: Cung cấp cơ sở thuật toán để xây dựng hệ thống gợi ý sản phẩm (Recommender Systems), phân tích giỏ hàng đa thời kỳ (Temporal Market Basket Analysis), phân tích hành trình khách hàng trên website và phát hiện bất thường trong chuỗi sự kiện an ninh mạng.
  • Phần đáng tham khảo nhất: Cấu trúc thuật toán TopKWFP (Chương 2), cấu trúc bảng lợi ích trong thuật toán HUISP (Chương 3) và các chứng minh tính đúng đắn, tính đầy đủ của các giải thuật.

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

1. Tại sao độ hỗ trợ có trọng số chuẩn hóa ($NWsupport$) không có tính chất phản đơn điệu và luận án xử lý vấn đề này như thế nào?

Trong khai phá dữ liệu truyền thống, tính phản đơn điệu quy định rằng nếu một dãy $\alpha$ không thường xuyên thì mọi dãy chứa $\beta \supset \alpha$ cũng không thể thường xuyên. Tuy nhiên, với trọng số chuẩn hóa $NW(\alpha) = \frac{1}{k}\sum w_j$, khi ghép thêm một mục mới có trọng số rất cao vào dãy ngắn, trọng số trung bình của dãy mới có thể tăng lên đáng kể, làm cho $NWsupport(\beta) \ge wminsup$ dù cho $NWsupport(\alpha) < wminsup$. Luận án khắc phục điều này bằng cách sử dụng cận trên $sup(\alpha) \times MaxW \ge wminsup$ (với $MaxW$ là trọng số lớn nhất trong toàn bộ CSDL). Cận trên này đảm bảo tính phản đơn điệu, cho phép cắt tỉa không gian tìm kiếm an toàn mà không bỏ sót nghiệm.

2. Bốn ràng buộc khoảng cách thời gian ($C_1, C_2, C_3, C_4$) trong luận án được phân loại đơn điệu và phản đơn điệu như thế nào?

  • Ràng buộc $C_1$ ($min_time_interval$), $C_2$ ($max_time_interval$) và $C_4$ ($max_whole_interval$) là các ràng buộc phản đơn điệu: Nếu một dãy không thỏa mãn một trong các ràng buộc này thì bất kỳ dãy cha nào mở rộng từ nó cũng chắc chắn vi phạm, cho phép cắt tỉa nhánh đệ quy ngay lập tức.
  • Ràng buộc $C_3$ ($min_whole_interval$) là ràng buộc đơn điệu: Nếu một dãy thỏa mãn khoảng cách tối thiểu từ đầu đến cuối thì các dãy mở rộng tiếp theo từ nó cũng sẽ thỏa mãn. Do đó, $C_3$ không thể dùng để tỉa nhánh sớm mà được dùng để kiểm tra điều kiện xuất kết quả cuối cùng.

3. Thuật toán TopKWFP giải quyết vấn đề gì vượt trội so với WIPrefixSpan?

Thuật toán WIPrefixSpan đòi hỏi người dùng phải cung cấp trước ngưỡng hỗ trợ tối thiểu $wminsup$. Nếu đặt quá cao sẽ tìm thấy rất ít mẫu, nếu đặt quá thấp thuật toán sẽ chạy rất chậm do bùng nổ ứng viên. Thuật toán TopKWFP giải quyết triệt để vấn đề này bằng cách cho phép người dùng chỉ định trực tiếp số lượng $k$ mẫu mong muốn. Thuật toán khởi tạo ngưỡng động $\varepsilon = 0$ và tự động nâng dần $\varepsilon$ lên khi tìm thấy các mẫu có $NWsupport$ cao hơn để lấp đầy danh sách $k$ phần tử, qua đó tối ưu hóa việc cắt tỉa không gian tìm kiếm một cách tự động.

4. Điểm khác biệt cốt lõi giữa thuật toán UIPrefixSpan (2 pha) và HUISP (1 pha) là gì?

  • UIPrefixSpan (2 pha): Sử dụng độ đo $SWU$ trong pha 1 để sinh ra tập ứng viên tiềm năng (HTSP) bằng phương pháp tạo CSDL chiếu đệ quy, sau đó ở pha 2 phải duyệt lại CSDL để tính toán lợi ích thực tế của từng ứng viên và lọc bỏ các mẫu không đạt.
  • HUISP (1 pha): Sử dụng cấu trúc bảng lợi ích (Utility Table) và bảng chỉ mục lưu thông tin thời gian, tính toán trực tiếp các cận trên lợi ích chặt hơn trong bộ nhớ, khai phá trực tiếp các mẫu dãy lợi ích cao mà không cần tạo CSDL chiếu đệ quy và không cần pha kiểm tra lại, giúp tiết kiệm bộ nhớ và rút ngắn thời gian thực thi.

Kết luận

Luận án tiến sĩ của tác giả Trần Huy Dương đã giải quyết trọn vẹn và có hệ thống bài toán khai phá mẫu dãy có trọng số trong cơ sở dữ liệu dãy có khoảng cách thời gian và cơ sở dữ liệu dãy định lượng. Bằng việc đề xuất ba thuật toán mới gồm TopKWFP, UIPrefixSpan và HUISP, luận án đã khắc phục các hạn chế lớn của các phương pháp truyền thống về tính phi phản đơn điệu của trọng số, việc phụ thuộc vào ngưỡng hỗ trợ cố định và chi phí tính toán hai pha trong khai phá lợi ích cao. Các kết quả nghiên cứu đều được chứng minh toán học chặt chẽ về tính đúng đắn, tính đầy đủ và được kiểm chứng thực nghiệm xác thực trên các bộ dữ liệu chuẩn, mang lại giá trị khoa học và giá trị ứng dụng thực tiễn cao trong phân tích dữ liệu chuỗi thời gian.