Tổng quan về luận án

Khai phá mẫu dãy (Sequential Pattern Mining - SPM) là một trong những bài toán nền tảng và cốt lõi nhất của lĩnh vực Khai phá dữ liệu (Data Mining) và Trí tuệ nhân tạo. Kể từ công trình đặt nền móng của Agrawal và Srikant (1995), mục tiêu trung tâm của SPM là trích xuất toàn bộ các mẫu dãy con thường xuyên xuất hiện trong cơ sở dữ liệu dãy (Sequence Database - SDB) thỏa mãn một ngưỡng hỗ trợ tối thiểu ($minsup$) định trước. Tuy nhiên, các mô hình tiếp cận truyền thống bộc lộ ba điểm nghẽn lý thuyết và thực tiễn nghiêm trọng:

  1. Giả định tất cả các mục dữ liệu (items) đều có tầm quan trọng ngang nhau, bỏ qua trọng số thực tế (item weights) phản ánh giá trị chiến lược hay giá cả của từng mặt hàng;
  2. Xem xét sự xuất hiện của các mục dưới dạng nhị phân ($0/1$), bỏ qua yếu tố số lượng mua (quantity/internal utility) và mức sinh lời biên (external utility);
  3. Bỏ qua khoảng cách thời gian (time intervals) giữa các sự kiện trong chuỗi, khiến thông tin về độ trễ hành vi bị triệt tiêu hoàn toàn.

Trước bối cảnh khoa học đó, luận án tiến sĩ với tiêu đề "Khai phá mẫu dãy có trọng số trong Cơ sở dữ liệu dãy" do Nghiên cứu sinh (NCS) Trần Huy Dương thực hiện dưới sự hướng dẫn khoa học của TS. Nguyễn Trường Thắng và GS. Vũ Đức Thi tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam (chuyên ngành Hệ thống thông tin, Mã số: 9 48 01 04, bảo vệ năm 2021) đã tạo nên một bước đột phá học thuật quan trọng. Luận án thiết lập khung lý thuyết và hệ thống giải thuật tiên tiến nhằm giải quyết trọn vẹn sự kết hợp giữa trọng số, số lượng định lượng và khoảng cách thời gian trong cơ sở dữ liệu chuỗi.

Khoảng trống nghiên cứu (Research Gaps)

Dựa trên việc tổng hợp các công trình quốc tế kinh điển, luận án nhận diện hai khoảng trống nghiên cứu then chốt:

  • Research Gap 1: Trong cơ sở dữ liệu dãy có khoảng cách thời gian ($iSDB$), việc xác định ngưỡng hỗ trợ trọng số tối thiểu ($wminsup$) rất khó khăn đối với người dùng nếu không có hiểu biết sâu về phân phối dữ liệu. Các thuật toán khai phá top-$k$ truyền thống như TKS của Fournier-Viger và cộng sự (2013) hay các thuật toán trọng số như WIPrefixSpan của Dương và cộng sự (2015) chưa tích hợp đồng thời việc khai phá top-$k$ với trọng số chuẩn hóa và hệ ràng buộc thời gian 4 tham số ($C_1, C_2, C_3, C_4$).
  • Research Gap 2: Trong cơ sở dữ liệu dãy định lượng có khoảng cách thời gian ($QiSDB$), việc khai phá mẫu dãy lợi ích cao (High Utility Sequential Pattern Mining - HUSPM) đối mặt với thách thức bùng nổ không gian tìm kiếm do hàm lợi ích không có tính phản đơn điệu (non-anti-monotonicity). Các công trình quốc tế như UL, US của Ahmed và cộng sự (2010), USpan của Yin và cộng sự (2012), hay HUSPM của Truong-Chi và Fournier-Viger (2019) chưa hỗ trợ cấu trúc khoảng cách thời gian thực giữa các giao dịch, hoặc các thuật toán mờ như FSPFTIM của Phương và cộng sự (2018) chỉ dừng lại ở xấp xỉ mờ dựa trên phương pháp Apriori duyệt dữ liệu nhiều lần với chi phí tính toán rất lớn.

Câu hỏi nghiên cứu và Giả thuyết khoa học

Luận án tập trung giải quyết 3 câu hỏi nghiên cứu cốt lõi:

  • RQ1: Làm thế nào để khai phá chính xác tập top-$k$ mẫu dãy có trọng số trong $iSDB$ mà không cần thiết lập $minsup$ tĩnh, đồng thời thỏa mãn đồng thời 4 ràng buộc thời gian đa cấp?
  • RQ2: Cơ chế chặn trên (upper bound) và cấu trúc biểu diễn nào cho phép khai phá mẫu dãy lợi ích cao trong $QiSDB$ có khoảng cách thời gian theo mô hình 2 pha mà vẫn đảm bảo tính đúng đắn và đầy đủ?
  • RQ3: Có thể loại bỏ hoàn toàn giai đoạn sinh ứng viên trung gian (candidate generation) để xây dựng một thuật toán 1 pha (one-phase) trực tiếp khai phá mẫu dãy lợi ích cao với thời gian tuyến tính và tối ưu bộ nhớ hay không?

Hệ thống giả thuyết nghiên cứu tương ứng:

  • H1: Một chiến lược nâng ngưỡng động $\varepsilon$ kết hợp với cấu trúc cơ sở dữ liệu chiếu theo tiền tố (Prefix-projected) sẽ giảm thiểu số lượng ứng viên cần duyệt xuống cấp số nhân so với việc quét lặp $minsup$.
  • H2: Việc áp dụng cận trên trọng số tối đa $MaxW = \max_{i_j \in I}(w_j)$ và độ đo $SWU$ (Sequence-Weighted Utility) có khả năng khôi phục tính chất phản đơn điệu để tỉa sớm các nhánh tìm kiếm vô hiệu.
  • H3: Cấu trúc Bảng Lợi Ích (Utility Table / Index Table) cho phép xác định chính xác giá trị lợi nhuận chuỗi trong 1 pha duy nhất, giúp giảm hơn 70% bộ nhớ sử dụng so với tiếp cận 2 pha truyền thống.

Khung lý thuyết và Phạm vi nghiên cứu

  • Theoretical Framework: Lý thuyết tăng trưởng mẫu dãy (Pattern-growth paradigm), Lý thuyết khai phá lợi ích (Utility mining theory), Lý thuyết ràng buộc thời gian phản đơn điệu và đơn điệu (Monotonic & Anti-monotonic constraint theory).
  • Scope & Data: Không gian mục từ $I = {i_1, i_2, \dots, i_n}$, cấu trúc dữ liệu chuỗi thời gian giao dịch khách hàng, các bộ dữ liệu chuẩn quốc tế từ kho lưu trữ UCI Machine Learning Repository và tập dữ liệu mô phỏng tổng hợp quy mô lớn.
  • Quantified Impact: Đề xuất 3 thuật toán hoàn toàn mới gồm TopKWFP, UIPrefixSpan và HUISP, đạt tốc độ thực thi nhanh hơn từ 3 đến 5 lần và tiết kiệm 60-80% dung lượng bộ nhớ so với các thuật toán cơ sở tương đương.

Literature Review và Positioning

Lịch sử phát triển của SPM trải qua 4 giai đoạn tiến hóa rõ rệt, định hình nên bối cảnh lý thuyết của luận án:

[Khai phá tuần tự kinh điển] ---> [Khai phá có trọng số]
  - AprioriAll, GSP (1995-1996)       - MWSP (2000), WSpan (2008)
  - SPADE, SPAM, PrefixSpan (2000-2004) - WIPrefixSpan (2015)
              |                                  |
              v                                  v
[Khai phá ràng buộc thời gian]  ---> [Khai phá lợi ích cao định lượng]
  - cSpade, I-PrefixSpan (2000-2003)    - UL, US, USpan (2010-2012)
  - Hirate & Yamana (2006)              - HUS-Span, HUSPM (2016-2019)

  1. Nhóm thuật toán tuần tự kinh điển:

    • Phương pháp tìm kiếm theo chiều rộng (Breadth-First Search - BFS) dựa trên sinh ứng viên: AprioriAll (Agrawal & Srikant, 1995), GSP (Srikant & Agrawal, 1996). Hạn chế: duyệt CSDL nhiều lần, bùng nổ số lượng ứng viên $2^m$.
    • Phương pháp biểu diễn dọc (Vertical Format Mining): SPADE (Zaki, 2000) sử dụng IDList, SPAM (Ayres et al., 2002) dùng cấu trúc bit-vector, LAPIN (Yin et al., 2005), CM-SPAM/CM-SPADE (Fournier-Viger et al., 2014).
    • Phương pháp tăng trưởng tiền tố (Pattern-Growth): FreeSpan (Han et al., 2000), PrefixSpan (Pei et al., 2001, 2004). Ưu điểm vượt trội: tìm kiếm theo chiều sâu (Depth-First Search - DFS), chỉ xét các mẫu thực sự tồn tại trong CSDL thông qua cơ sở dữ liệu chiếu (projected database).

  2. Nhóm thuật toán có trọng số (Weighted SPM):

    • MWSP (Wei et al., 2000) mở rộng AprioriAll với trọng số mục; WSpan (Yun et al., 2008) mở rộng PrefixSpan sử dụng hằng số trọng số lớn nhất; WSPM (Tao et al.) dùng tích trọng số lớn nhất với độ dài chuỗi; WIPrefixSpan (Duong et al., 2015) khai phá chuỗi trọng số chuẩn hóa trong $iSDB$.

  3. Nhóm thuật toán có ràng buộc khoảng cách thời gian:

    • cSpade (Zaki, 2000), I-PrefixSpan (Chen et al., 2003), TGSP (Yen et al., 2013), TiWS (Chang, 2011), và giải thuật của Hirate & Yamana (2006) kết hợp ràng buộc thời gian với mở rộng CSDL dãy.

  4. Nhóm thuật toán lợi ích cao (High Utility SPM - HUSP):

    • UL, US (Ahmed et al., 2010), USpan (Yin et al., 2012) giới thiệu cây Utility-Tree, PHUS (Lan et al., 2014), HuspExt (Alkan et al., 2016), HUS-Span (Wang et al., 2016), HUSPM (Truong-Chi & Fournier-Viger, 2019).

Tranh luận học thuật và Định vị nghiên cứu

Trong y văn tồn tại hai cuộc tranh luận lớn:

  • Tranh luận 1 (Candidate Generation vs. Pattern-Growth): BFS tiêu tốn bộ nhớ khủng khiếp khi lưu trữ toàn bộ $k$-sequences để sinh $(k+1)$-sequences. PrefixSpan chứng minh tính ưu việt của DFS, nhưng việc tạo CSDL chiếu đệ quy lại tiêu tốn tài nguyên sao chép bộ nhớ.
  • Tranh luận 2 (Xử lý tính bất biến phản đơn điệu): Khi đưa trọng số hoặc hàm lợi ích vào, tính chất Apriori ($sup(\alpha) \ge sup(\beta)$ với $\alpha \subseteq \beta$) bị phá vỡ hoàn toàn. Một chuỗi con không thường xuyên vẫn có thể kết hợp với các mục có trọng số cao để trở thành chuỗi thường xuyên. Yun và cộng sự (2008) hay Ahmed và cộng sự (2010) buộc phải sử dụng các chặn trên lỏng lẻo ($SWU$), dẫn đến tập ứng viên giả (over-estimated candidates) quá lớn.

Luận án của NCS. Trần Huy Dương định vị chính xác tại giao điểm của 4 nhánh nghiên cứu: tích hợp mô hình trọng số chuẩn hóa, tính toán định lượng nội tại/ngoại tại, xử lý đồng thời 4 ràng buộc thời gian ($C_1, C_2, C_3, C_4$), và giải quyết triệt để bài toán tối ưu hóa 1 pha không cần sinh ứng viên trung gian. So với công trình của Hirate & Yamana (2006) và HUSPM của Truong-Chi & Fournier-Viger (2019), luận án giải quyết bài toán tổng quát và chặt chẽ hơn nhiều về mặt toán học.

Đó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 của Agrawal & Srikant (1995), Pei và cộng sự (2001), và Ahmed và cộng sự (2010) thông qua việc hệ thống hóa các định nghĩa toán học chuẩn xác:

Trích dẫn Định nghĩa từ luận án:

  1. Dãy dữ liệu có khoảng cách thời gian ($iSDB$): $$S = \langle(t_{1,1}, s_1), (t_{1,2}, s_2), \dots, (t_{1,m}, s_m)\rangle$$ trong đó $t_{1,j} = s_j.time - s_1.time$ là khoảng cách thời gian giữa tập mục $s_1$ và $s_j$.
  2. Trọng số chuẩn hóa của dãy ($NW$): Cho dãy $\alpha$ có độ dài $k$, trọng số chuẩn hóa được định nghĩa: $$NW(\alpha) = \frac{1}{k} \sum_{i_j \in \alpha} w_j \quad (w_j \in [0, 1])$$
  3. Độ hỗ trợ với trọng số của dãy ($NWsupport$): $$NWsupport(\alpha) = NW(\alpha) \times sup(\alpha) = \left(\frac{1}{k} \sum_{i_j \in \alpha} w_j\right) \times sup(\alpha)$$
  4. Hệ 4 ràng buộc khoảng cách thời gian:
    • $C_1 = min_time_interval$: $t_{i, i+1} \ge C_1$ (Ràng buộc phản đơn điệu)
    • $C_2 = max_time_interval$: $t_{i, i+1} \le C_2$ (Ràng buộc phản đơn điệu)
    • $C_3 = min_whole_interval$: $t_{1, m} \ge C_3$ (Ràng buộc đơn điệu)
    • $C_4 = max_whole_interval$: $t_{1, m} \le C_4$ (Ràng buộc phản đơn điệu) với các điều kiện logic bắt buộc: $C_1 \le C_2$, $C_3 \le C_4$, $C_1 \le C_4$, $C_2 \le C_4$.
                    Mô hình Ràng buộc Thời gian Đa cấp
       s1 ------------ s2 ------------ s3 -------------------- sm
       |   t_{1,2}     |   t_{2,3}     |                       |
       |<------------->|<------------->|                       |
          C1 <= t_{i,i+1} <= C2                                |
       |<----------------------------------------------------->|
                          C3 <= t_{1,m} <= C4

Khung phân tích độc đáo

Để vượt qua rào cản phi phản đơn điệu, luận án chứng minh định lý về Mẫu dãy ứng viên trọng số với khoảng cách thời gian: $$\text{Dãy } \alpha \text{ là ứng viên nếu: } sup(\alpha) \times MaxW \ge wminsup \land \alpha \text{ thỏa mãn } C_1, C_2, C_3, C_4$$ trong đó $MaxW = \max_{i_j \in I}(w_j)$. Vì $MaxW$ là hằng số cực đại, hàm $sup(\alpha) \times MaxW$ hoàn toàn bảo toàn tính phản đơn điệu, cho phép tỉa an toàn toàn bộ các không gian con mà không bỏ sót bất kỳ mẫu thường xuyên trọng số nào.

       [Không gian toàn bộ chuỗi]
                   |
     (Tỉa bằng sup(α) * MaxW >= wminsup) ---> Đảm bảo Anti-monotonicity
                   v
       [Tập ứng viên rút gọn]
                   |
     (Lọc bằng NWsupport(α) >= wminsup & C1, C2, C3, C4)
                   v
       [Tập mẫu dãy thường xuyên trọng số chính xác]

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

Thiết kế nghiên cứu

  • Triết lý khoa học: Thực chứng luận (Positivism) kết hợp phương pháp Toán - Tin kiến tạo hình thức. Mọi mệnh đề và định lý đều được diễn giải bằng ký hiệu toán học chặt chẽ và chứng minh tính đúng đắn (Soundness) cùng tính đầy đủ (Completeness).
  • Thiết kế đa cấp: Luận án tiếp cận từ cấp độ biểu diễn dữ liệu cơ bản ($SDB \to iSDB \to QiSDB$), xây dựng chiến lược duyệt không gian trạng thái (DFS trên cây tiền tố), đến cấu trúc chỉ mục và bảng tiện ích tối ưu bộ nhớ.
       Cơ sở dữ liệu dãy (SDB)
                |
                +---> CSDL dãy có khoảng cách thời gian (iSDB)
                |        |
                |        +---> Thuật toán TopKWFP (Top-k Weighted)
                |
                +---> CSDL dãy định lượng có khoảng cách thời gian (QiSDB)
                         |
                         +---> Thuật toán UIPrefixSpan (2-phase HUSP)
                         |
                         +---> Thuật toán HUISP (1-phase Utility Table)

Quy trình nghiên cứu và Hệ thuật toán đề xuất

1. Thuật toán TopKWFP (Top-k Weighted Sequential Patterns with item interval)

Giải quyết bài toán tìm $k$ mẫu dãy có $NWsupport$ cao nhất thỏa mãn $C_1, C_2, C_3, C_4$.

  • Chiến lược tối ưu: Khởi tạo ngưỡng động $\varepsilon = 0$. Sử dụng cấu trúc hàng đợi ưu tiên (Priority Queue) kích thước $k$. Khi tập kết quả đạt $k$ phần tử, $\varepsilon$ được nâng lên bằng giá trị $NWsupport$ nhỏ nhất trong hàng đợi: $\varepsilon = \min {NWsupport(t) \mid t \in \mathcal{T}}$. Mọi ứng viên có $sup(\alpha) \times MaxW < \varepsilon$ lập tức bị loại bỏ khỏi các bước duyệt đệ quy tiếp theo.

2. Thuật toán UIPrefixSpan (2-phase Utility Interval PrefixSpan)

Khai phá mẫu dãy lợi ích cao trong $QiSDB$ có khoảng cách thời gian dựa trên mô hình tăng trưởng tiền tố 2 pha:

  • Pha 1: Sử dụng giới hạn trên $SWU$ (Sequence-Weighted Utility) để sinh tập ứng viên tiềm năng (Candidate High Utility Sequences - CHUS) thỏa mãn ràng buộc thời gian.
  • Pha 2: Quét lại CSDL chiếu để tính toán chính xác giá trị lợi nhuận thực tế $u(\alpha)$ và lọc ra tập mẫu lợi ích cao thực sự ($HUSP$).

3. Thuật toán HUISP (High Utility Item Interval Sequential Pattern - 1 pha)

Đột phá công nghệ lớn nhất của luận án:

  • Loại bỏ hoàn toàn Pha 1 và Pha 2 trung gian.
  • Sử dụng cấu trúc Bảng Lợi Ích (Utility Table / Index Table) gắn kèm trong từng bước chiếu CSDL. Bảng lưu trữ trực tiếp thông tin định lượng, lợi nhuận cục bộ và khoảng cách thời gian của từng mục ứng viên mở rộng. Nhờ đó, việc kiểm tra điều kiện lợi ích và ràng buộc thời gian diễn ra đồng thời trong 1 lần duyệt duy nhất.

Dữ liệu và Phân tích thực nghiệm

  • Môi trường thử nghiệm: Cài đặt bằng C++/Java trên hệ thống máy tính tiêu chuẩn; chạy thực nghiệm trên các tập dữ liệu benchmark chuẩn quốc tế từ kho UCI Machine Learning Repository (như chuỗi giao dịch bán lẻ, chuỗi clickstream web, dữ liệu phân tích thị trường) và các bộ dữ liệu mô phỏng tổng hợp với kích thước từ vài chục nghìn đến hàng triệu giao dịch.
  • Tham số đánh giá:
    • Thời gian chạy (Execution time tính bằng giây/mili-giây);
    • Bộ nhớ tiêu thụ (Memory usage tính bằng MB);
    • Số lượng mẫu ứng viên sinh ra so với số mẫu thực sự thỏa mãn;
    • Tác động của việc thay đổi tham số $k$, ngưỡng $wminsup$, ngưỡng lợi ích tối thiểu $min_util$, và biên độ ràng buộc khoảng cách thời gian ($C_1, C_2, C_3, C_4$).

Phát hiện đột phá và implications

Những phát hiện then chốt

  1. Khắc phục triệt để hiện tượng bùng nổ ứng viên trong Top-k Mining: Thuật toán TopKWFP với cơ chế nâng ngưỡng động $\varepsilon$ giúp thu hẹp không gian tìm kiếm tới 85% so với phương pháp thử - sai (trial-and-error) nhiều lần của WIPrefixSpan. Khi tham số $k$ tăng từ 100 đến 10.000, thời gian thực thi của TopKWFP chỉ tăng tuyến tính chứ không bùng nổ theo hàm mũ.
  2. Hiệu năng vượt trội của mô hình 1 pha HUISP so với 2 pha UIPrefixSpan: Dữ liệu thực nghiệm trên 1000 mục với phân phối lợi nhuận thực tế cho thấy:
    • Thuật toán HUISP giảm từ 70% đến 90% số lượng mẫu dãy ứng viên trung gian so với UIPrefixSpan;
    • Thời gian xử lý của HUISP nhanh hơn từ 3.2 đến 4.8 lần so với UIPrefixSpan trên cùng một bộ dữ liệu $QiSDB$;
    • Mức tiêu thụ bộ nhớ RAM của HUISP được duy trì ổn định ở mức thấp nhờ cấu trúc Utility Table giải phóng ngay các nhánh chiếu không khả thi.
  3. Hiệu ứng sàng lọc kép của hệ ràng buộc thời gian ($C_1, C_2, C_3, C_4$): Thực nghiệm chứng minh rằng việc áp dụng đồng thời các ràng buộc thời gian cục bộ ($C_1, C_2$) và toàn cục ($C_3, C_4$) đóng vai trò như một bộ lọc không gian trạng thái mạnh mẽ. Cụ thể, khi siết chặt $C_2$ (khoảng cách tối đa giữa 2 sự kiện liền kề) và $C_4$ (tổng thời gian chuỗi), số lượng mẫu dãy cần xét giảm từ $10^6$ xuống còn vài nghìn mẫu mà không làm sai lệch các quy luật hành vi thực tế.
  4. Phân phối lợi nhuận thực tế có tính chất đuôi dài (Long-tail Distribution): Trong CSDL định lượng $QiSDB$, các mặt hàng có tần suất xuất hiện cực cao (high support) thường có tỷ suất sinh lời thấp, trong khi các mẫu dãy có lợi nhuận cao nhất lại tập trung ở nhóm mặt hàng có tần suất trung bình nhưng giá trị biên lớn. Điều này chứng minh các phương pháp SPM truyền thống chỉ dựa vào $minsup$ đã bỏ sót hoàn toàn các tri thức kinh doanh sinh lời cao nhất.
       So sánh Hiệu năng giữa UIPrefixSpan (2-phase) và HUISP (1-phase)
       -----------------------------------------------------------------
       Chỉ số đánh giá            UIPrefixSpan           HUISP (Đột phá)
       -----------------------------------------------------------------
       Cơ chế thực thi            2 Pha (Sinh & Lọc)     1 Pha (Utility Table)
       Số ứng viên rác            Rất lớn (CHUS)         Giảm 70% - 90%
       Thời gian chạy             Cơ sở (1.0x)           Nhanh hơn 3.2x - 4.8x
       Bộ nhớ tiêu thụ            Cao (Lưu CHUS)         Tiết kiệm 60% - 80%
       Độ phức tạp chiếu          Duyệt lặp đệ quy       Chiếu đơn kèm chỉ mục
       -----------------------------------------------------------------

Implications đa chiều

  • Về mặt học thuật: Luận án mở ra hướng tiếp cận chuẩn hóa cho việc tích hợp các thuộc tính phi đơn điệu (non-anti-monotonic attributes) vào cấu trúc tăng trưởng tiền tố DFS, cung cấp bằng chứng toán học vững chắc cho việc thiết kế các thuật toán khai phá mẫu nâng cao.
  • Về mặt công nghệ và R&D: Cung cấp giải thuật có khả năng nhúng trực tiếp vào các động cơ phân tích dữ liệu lớn (Big Data Analytics Engines) trong các hệ thống gợi ý (Recommender Systems), phân tích chuỗi nhấp chuột (Clickstream Mining), và tin sinh học (phân tích chuỗi gen DNA/Protein có trọng số phân tử và khoảng cách vị trí).
  • Về mặt quản trị kinh doanh: Giúp các nhà bán lẻ và doanh nghiệp thương mại điện tử nhận diện chính xác: "Khách hàng mua sản phẩm A, sau bao nhiêu ngày sẽ mua tiếp sản phẩm B và C với số lượng bao nhiêu để tối đa hóa doanh thu", từ đó thiết kế các chiến dịch cross-selling, up-selling và quản trị kho vận (supply chain inventory) chính xác theo mốc thời gian thực.

Limitations và Future Research

Luận án thẳng thắn thừa nhận 4 giới hạn nghiên cứu:

  1. Kiến trúc xử lý đơn máy (Single-node Memory): Các thuật toán hiện tại được tối ưu hóa trên bộ nhớ trong của một máy tính đơn lẻ, chưa được phân tán hóa trên các framework tính toán song song quy mô lớn như Apache Spark hay Flink.
  2. Khoảng cách thời gian dạng rời rạc (Discrete Time Intervals): Mô hình hiện tại giả định thời gian là các giá trị số nguyên rời rạc (ngày, giờ), chưa hỗ trợ các biến thời gian liên tục hoặc logic thời gian mờ phi tuyến phức tạp.
  3. Thiết lập tham số $min_util$ trong HUISP: Mặc dù TopKWFP đã tự động hóa việc tìm kiếm top-$k$, thuật toán HUISP vẫn yêu cầu người dùng chỉ định ngưỡng lợi nhuận tối thiểu $min_util$.
  4. Chưa khai phá mẫu đóng (Closed Patterns) và mẫu cực đại (Maximal Patterns): Tập kết quả trả về vẫn bao gồm toàn bộ các mẫu con thường xuyên, có thể gây ra hiện tượng dư thừa thông tin (pattern redundancy).

Chương trình nghiên cứu tương lai (Future Agenda)

  • Hướng 1: Phát triển phiên bản phân tán song song (Distributed HUISP) trên nền tảng Spark GraphX/RDD để xử lý các tập dữ liệu quy mô hàng tỷ chuỗi giao dịch.
  • Hướng 2: Tích hợp logic mờ (Fuzzy Logic) để tự động ánh xạ các khoảng cách thời gian liên tục thành các khái niệm ngữ nghĩa mờ sinh động ("ngay lập tức", "ngắn hạn", "dài hạn").
  • Hướng 3: Mở rộng bài toán sang khai phá mẫu dãy lợi ích cao đóng (Closed High Utility Sequential Patterns) và mẫu cực đại nhằm nén không gian kết quả mà không làm mất mát thông tin lợi nhuận.
  • Hướng 4: Áp dụng mô hình giải thuật vào các luồng dữ liệu thời gian thực (Data Streams) với cơ chế cửa sổ trượt (Sliding Window).

Tác động và ảnh hưởng

  • Tác động học thuật quốc tế: Các kết quả cốt lõi của luận án đã được công bố trên 05 công trình khoa học uy tín (từ [CT1] đến [CT5]) tại các hội nghị và tạp chí chuyên ngành Hệ thống thông tin và Khoa học máy tính. Khung lý thuyết của luận án đóng góp nguồn trích dẫn giá trị cho cộng đồng nghiên cứu khai phá dữ liệu chuỗi quốc tế.
  • Chuyển đổi công nghiệp bán lẻ và Logistic: Thuật toán cung cấp công cụ lõi để tự động hóa việc phân tích giỏ hàng đa thời kỳ (Multi-period Market Basket Analysis), giúp các sàn thương mại điện tử tối ưu hóa chi phí quảng cáo mục tiêu dựa trên thời gian trễ của hành vi mua sắm lặp lại.
  • An ninh mạng và Y tế thông minh: Khả năng xử lý chuỗi sự kiện có khoảng cách thời gian và mức độ nguy hại (trọng số) là nền tảng lý tưởng để xây dựng các hệ thống phát hiện xâm nhập mạng (Intrusion Detection Systems - IDS) và hệ thống dự đoán biến chứng bệnh án điện tử (Electronic Health Records - EHR).

Đối tượng hưởng lợi

  • Nghiên cứu sinh và Giới học thuật: Tiếp cận một khung phân tích toán học mẫu mực về xử lý tính phi phản đơn điệu, kế thừa mã nguồn và mô hình chứng minh định lý cận trên ($Upper-bound$).
  • Kỹ sư dữ liệu và Kiến trúc sư phần mềm (Data Engineers & Architects): Có sẵn mã giả và quy trình tối ưu hóa bộ nhớ 1 pha để tích hợp trực tiếp vào các nền tảng Data Warehouse và BI.
  • Giám đốc kinh doanh và Nhà phân tích dữ liệu (BI / Marketing Directors): Sở hữu công cụ phân tích hành vi khách hàng chính xác theo 3 trục: Tần suất - Lợi nhuận - Khoảng thời gian.
  • Cơ quan quản lý và hoạch định chính sách số: Cơ sở khoa học để thiết kế các hệ thống phân tích dữ liệu công cộng thông minh (giao thông, y tế dự phòng, giám sát an toàn thông tin quốc gia).

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 thiết lập Mô hình Khai phá Mẫu dãy Trọng số Chuẩn hóa kết hợp Hệ Ràng buộc Thời gian 4 Tham số và Cơ chế Cận trên $MaxW$-Pruning. Công trình đã mở rộng trực tiếp Lý thuyết Tăng trưởng Tiền tố (Prefix-growth Theory) của Pei và cộng sự (2001) và Lý thuyết Khai phá Lợi ích Dãy (Sequence Utility Mining) của Ahmed và cộng sự (2010), giải quyết thành công bài toán bảo toàn tính phản đơn điệu trong không gian chuỗi có trọng số và khoảng cách thời gian.

2. Đột phá phương pháp luận so với các nghiên cứu quốc tế tương đương?

So với thuật toán 2 pha truyền thống của Ahmed và cộng sự (2010) và giải thuật ràng buộc thời gian của Hirate & Yamana (2006), luận án đã tạo nên bước nhảy vọt với thuật toán HUISP 1 pha. Bằng việc sáng tạo cấu trúc Bảng Lợi Ích (Utility Table), HUISP tính toán trực tiếp lợi nhuận chuỗi và kiểm tra ràng buộc thời gian ngay trong quá trình chiếu CSDL, triệt tiêu hoàn toàn pha sinh ứng viên $CHUS$ tốn kém, giúp tăng tốc độ xử lý lên 3-5 lần và giảm 80% bộ nhớ.

3. Phát hiện bất ngờ nhất từ dữ liệu thực nghiệm là gì?

Phát hiện bất ngờ nhất là Quy luật tương hỗ giữa Ràng buộc Thời gian Cục bộ ($C_2$) và Cận trên Trọng số ($MaxW$): Khi áp dụng đồng thời hai điều kiện này, tốc độ cắt tỉa không gian tìm kiếm không chỉ là phép cộng tuyến tính mà tăng trưởng theo cấp số nhân. Việc giới hạn khoảng cách giữa hai giao dịch liên tiếp ($C_2$) làm triệt tiêu phần lớn các chuỗi dài vô nghĩa trước cả khi hàm tính toán trọng số phức tạp phải kích hoạt.

4. Luận án có cung cấp quy trình tái lập thực nghiệm (Replication Protocol) không?

Có. Luận án mô tả chi tiết:

  • Cấu trúc các bảng dữ liệu chuẩn hóa: $SDB$, $iSDB$, $QiSDB$, Bảng trọng số mục, Bảng lợi ích ngoài, Bảng chỉ mục và CSDL chiếu theo tiền tố;
  • Từng bước thực thi của các giải thuật thông qua các ví dụ số học minh họa từng bước (Trace examples từ Bảng 1.1 đến 1.19);
  • Quy chuẩn tham chiếu các tập dữ liệu công khai từ kho lưu trữ chuẩn quốc tế UCI Machine Learning Repository.

5. Chương trình nghị sự nghiên cứu 10 năm được vạch ra như thế nào?

Lộ trình 10 năm tập trung vào:

  1. Chuyển đổi toàn bộ hệ thuật toán sang mô hình tính toán lượng tử/phân tán trên nền tảng Big Data Cloud;
  2. Tích hợp mạng nơ-ron sâu (Deep Learning) và đồ thị tri thức (Knowledge Graphs) với các luật chuỗi lợi ích cao có ràng buộc thời gian để dự báo hành vi tự động;
  3. Ứng dụng phổ quát hóa trong y học chính xác (Precision Medicine) và tối ưu hóa năng lượng lưới điện thông minh (Smart Grid).

Kết luận

Luận án tiến sĩ của NCS. Trần Huy Dương là một công trình khoa học công phu, mẫu mực, giải quyết trọn vẹn những thách thức cốt lõi của bài toán khai phá mẫu dãy hiện đại.

Các đóng góp mang tính nền tảng bao gồm:

  1. Thiết lập khung toán học chuẩn xác cho bài toán khai phá mẫu dãy trọng số chuẩn hóa và mẫu dãy lợi ích cao trong cơ sở dữ liệu dãy có khoảng cách thời gian thực;
  2. Đề xuất thuật toán TopKWFP khai phá top-$k$ mẫu dãy trọng số có khoảng cách thời gian với cơ chế nâng ngưỡng động $\varepsilon$, loại bỏ sự phụ thuộc vào tham số $minsup$ tĩnh;
  3. Đề xuất thuật toán 2 pha UIPrefixSpan đặt nền móng cho việc kết hợp khai phá lợi ích cao và ràng buộc khoảng cách thời gian 4 tham số trong $QiSDB$;
  4. Đột phá với thuật toán 1 pha HUISP sử dụng cấu trúc Bảng Lợi Ích tiên tiến, loại bỏ hoàn toàn giai đoạn sinh ứng viên trung gian, tối ưu hóa vượt bậc về thời gian và bộ nhớ;
  5. Chứng minh toán học chặt chẽ tính đúng đắn, tính đầy đủ và đánh giá độ phức tạp tính toán của toàn bộ hệ thuật toán;
  6. Kiểm chứng thực nghiệm quy mô lớn trên các tập dữ liệu chuẩn quốc tế UCI, chứng minh tính khả thi, độ tin cậy và giá trị ứng dụng thực tiễn to lớn trong kỷ nguyên chuyển đổi số và phân tích dữ liệu lớn.