Tổng quan luận án

Luận án tiến sĩ "Nghiên cứu phát hiện luật kết hợp hiếm và ứng dụng" được nghiên cứu sinh Cù Thu Thủy thực hiện dưới sự hướng dẫn khoa học của PGS. TS. Hà Quang Thụy, bảo vệ năm 2013 tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, thuộc chuyên ngành Hệ thống thông tin (mã số: 62 48 05 01).

  • Tính cấp thiết và khoảng trống nghiên cứu: Lý thuyết khai phá luật kết hợp (Association Rule Mining - ARM) do Rakesh Agrawal và cộng sự đề xuất năm 1993 chủ yếu tập trung vào việc tìm kiếm các mẫu phổ biến có độ hỗ trợ (support) và độ tin cậy (confidence) cao. Tuy nhiên, trong thực tiễn tại nhiều lĩnh vực như thương mại, y tế, sinh học và tài chính - ngân hàng, các sự kiện ít xảy ra (tần suất thấp) lại mang giá trị hỗ trợ quyết định đặc biệt quan trọng (ví dụ: tác dụng phụ tiêu cực của thuốc hạ lipid máu Cerivastatin, hay mối liên hệ giữa các mặt hàng giá trị cao như máy pha cà phê và máy xay cà phê). Khi áp dụng các thuật toán truyền thống (như Apriori) để tìm các luật hiếm, việc thiết lập ngưỡng độ hỗ trợ cực tiểu ($minSup$) xuống mức rất thấp làm bùng nổ không gian tìm kiếm, sinh ra số lượng khổng lồ các tập ứng viên không phổ biến, đòi hỏi chi phí tính toán và bộ nhớ cực lớn nhưng lại tạo ra nhiều luật dư thừa. Hai hướng tiếp cận chính trước đó gồm: sử dụng ràng buộc hệ quả (đòi hỏi phải biết trước thuộc tính hệ quả) và thiết lập đường biên phân chia (thường tìm kiếm từ dưới lên hoặc sinh tất cả các tập không phổ biến). Đồng thời, việc phát hiện luật kết hợp hiếm trên cơ sở dữ liệu (CSDL) định lượng hầu như chưa được giải quyết thấu đáo, mới chỉ dừng lại ở các tập chứa thuần túy các mục không phổ biến mà bỏ qua các trường hợp kết hợp giữa mục phổ biến và không phổ biến.

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

    1. Phát triển cơ sở lý thuyết và đề xuất các thuật toán hiệu quả nhằm phát hiện luật kết hợp hiếm trên cả hai loại CSDL tác vụ (nhị phân) và CSDL định lượng.
    2. Tập trung giải quyết Giai đoạn 1 của quy trình khai phá luật kết hợp hiếm (tìm kiếm các tập mục dữ liệu hiếm tương ứng), vốn là giai đoạn phức tạp nhất với độ phức tạp tính toán lý thuyết lên tới $O(2^{|I|})$.
    3. Triển khai ứng dụng thử nghiệm các kết quả nghiên cứu lý thuyết vào giải quyết các bài toán phân tích và dự báo kinh tế lượng cụ thể trong thực tiễn.

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

    • Đối tượng nghiên cứu: Các mô hình biểu diễn luật kết hợp hiếm (đặc biệt là luật Sporadic tuyệt đối, Sporadic không tuyệt đối, luật có ràng buộc mục dữ liệu âm), cấu trúc dàn Galois/toán tử đóng trong khai phá tập đóng, lý thuyết tập mờ (fuzzy sets) cho CSDL định lượng, và mô hình hồi quy chuyển tiếp trơn logistic (LSTR).
    • Phạm vi không gian và dữ liệu: Dữ liệu tác vụ nhị phân chuẩn (CSDL thực nghiệm Mushroom, các tệp CSDL tổng hợp $T5I1000D10K$, $T30I1000D10K$); dữ liệu định lượng được làm mờ; dữ liệu kinh tế lượng tại thị trường Việt Nam (chuỗi thời gian giao dịch chứng khoán của Sở Giao dịch Chứng khoán Hà Nội - HNX và chuỗi số liệu chỉ số giá tiêu dùng CPI cùng giá các nhóm hàng hóa liên quan).
    • Phạm vi nội dung: Luận án tập trung vào Giai đoạn 1 (khai phá tập mục hiếm đóng, tập mục hiếm mờ) nhằm hạn chế sinh luật dư thừa và tối ưu hóa không gian bộ nhớ.

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

Luận án đã hệ thống hóa lịch sử phát triển của lý thuyết khai phá luật kết hợp từ các nghiên cứu nền tảng đến các hướng mở rộng:

  • Các hướng nghiên cứu về luật kết hợp truyền thống và mở rộng:

    • Khai phá luật kết hợp phổ biến trên CSDL tác vụ: Khởi đầu từ công trình của R. Agrawal và cộng sự (1993, 1994) với thuật toán Apriori duyệt theo chiều rộng (BFS); thuật toán Partition của Savasere và cộng sự; các tiếp cận duyệt theo chiều sâu (DFS) như FP-Growth của Han và cộng sự, ECLAT của Zaki.
    • Khai phá tập phổ biến đóng và cực đại: Để khắc phục sự bùng nổ tổ hợp của tập phổ biến, Zaki và Hsiao (2002, 2005) đề xuất thuật toán CHARM dựa trên kết nối Galois; Pasquier và cộng sự đề xuất thuật toán CLOSE; Wang và cộng sự đề xuất CLOSET+. Về tập cực đại có Max-Miner (Bayardo, 1998), MAFIA (Burdick và cộng sự), GENMAX (Gouda và Zaki).
    • Khai phá với độ hỗ trợ khác nhau và có ràng buộc: Srikant và cộng sự (1997) đưa ra ràng buộc mục nhị phân; Liu và cộng sự (1999) đề xuất thuật toán MSApriori với ngưỡng hỗ trợ riêng $MIS(i)$ qua tham số $\beta$; Yun và cộng sự (2003) đề xuất thuật toán RSAA dựa trên độ hỗ trợ tương đối; Reddy và cộng sự đề xuất IMSApriori sử dụng độ sai biệt hỗ trợ $SD$; F. Tao và cộng sự (2003) nghiên cứu luật kết hợp có trọng số dựa trên tính chất đóng của trọng số; Rahman và cộng sự (2007) phát triển kỹ thuật tìm tập đóng có trọng số; M. Karypis (2001) đề xuất LPMiner với ràng buộc độ hỗ trợ giảm dần theo độ dài; Wang và cộng sự (2005) đề xuất ràng buộc phân thùng ($bin$); E. Cohen và cộng sự (2001) dùng hàm băm bỏ qua $minSup$; Wang và cộng sự (2003) khai phá luật tin cậy dựa trên tính đóng không gian; Xiong và cộng sự (2006) đề xuất độ đo $H$-độ tin cậy nhằm khai phá các mẫu bó cụm cao (hyperclique).
    • Khai phá luật kết hợp định lượng và luật mờ: Srikant và Agrawal (1996) đề xuất kỹ thuật rời rạc hóa thuộc tính số thành các khoảng nhị phân; Kuok và cộng sự (1998) đưa ra khái niệm luật kết hợp mờ nhằm khắc phục hiện tượng "điểm biên gãy" (sharp boundary); A. Teuhola (2007) phát triển phương pháp phân hoạch mờ đa chiều từ trên xuống.

  • Các hướng nghiên cứu phát hiện luật kết hợp hiếm:

    • Ràng buộc hệ quả cố định: I. Rahal và cộng sự (2004) dùng cây SE-tree và P-tree; Li và cộng sự đưa ra tiếp cận Emerging Pattern (EP) với độ tin cậy 100%; Bayardo và cộng sự đề xuất thuật toán Dense-Miner dựa trên hệ số cải tiến $Imp(A \to C)$.
    • Đường biên phân chia giữa tập phổ biến và không phổ biến: L. Szathmary và cộng sự (2007, 2012) đề xuất Apriori-Rare, MRG-Exp, ARIMA và mô hình luật $mRG$ dựa trên tập hiếm sinh cực tiểu; L. Zhou và cộng sự (2007) đề xuất thuật toán MBS và HBS tìm luật giữa các mục không phổ biến trên cả dữ liệu tác vụ và định lượng; Troiano và cộng sự (2009) giới thiệu thuật toán Rarity tìm kiếm từ trên xuống (top-down).
    • Luật Sporadic: Y. Koh và Rountree (2005) đưa ra khái niệm luật Sporadic tuyệt đối và thuật toán Apriori-Inverse sử dụng ngưỡng hỗ trợ cận dưới tuyệt đối $minAS$; Y. Koh và cộng sự (2008) mở rộng sang luật Sporadic không tuyệt đối với 4 dạng phân loại và đề xuất thuật toán MIISR.

  • Khoảng trống luận án lựa chọn giải quyết: Các công trình về luật Sporadic (như Apriori-Inverse hay MIISR) chủ yếu kế thừa tư tưởng duyệt toàn bộ của Apriori, dẫn tới chi phí thời gian cao và tạo ra tập luật hiếm dư thừa lớn. Luận án lựa chọn giải quyết: (1) Đưa cấu trúc tập đóng Galois (tương đồng tư tưởng CHARM) vào bài toán khai phá luật Sporadic hai ngưỡng trên CSDL tác vụ; (2) Thiết lập khung toán học và thuật toán khai phá luật Sporadic mờ trên CSDL định lượng; (3) Tích hợp mẫu âm của luật kết hợp với mô hình kinh tế lượng phi tuyến STR nhằm nâng cao độ chính xác dự báo thực tiễn.

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

1. Cơ sở lý thuyết và khung phân tích

  • Định nghĩa toán học về luật kết hợp: Cho tập các mục dữ liệu $I = {i_1, i_2, \dots, i_n}$, tập định danh tác vụ $O = {t_1, t_2, \dots, t_m}$, CSDL tác vụ $D \subseteq I \times O$. Một tác vụ $t \in O$ biểu diễn dưới dạng véc tơ nhị phân $t[k] \in {0, 1}$.
    • Độ hỗ trợ của tập $X \subseteq I$: $sup(X) = |{t \in O \mid X \subseteq t}| / |O|$.
    • Luật kết hợp có dạng $X \to Y$ ($X, Y \subseteq I, X \cap Y = \emptyset$), với $sup(X \to Y) = sup(X \cup Y)$ và độ tin cậy $conf(X \to Y) = sup(X \cup Y) / sup(X)$.
  • Lý thuyết kết nối Galois và toán tử đóng: Ngữ cảnh khai phá dữ liệu $\hat{D} = (O, I, R)$. Ánh xạ Galois giữa $2^O$ và $2^I$: $$f(O) = {i \in I \mid \forall t \in O, (i, t) \in R}, \quad g(I) = {t \in O \mid \forall i \in I, (i, t) \in R}$$ Toán tử đóng Galois $h = f \circ g$ trên $2^I$. Tập $X$ là tập đóng nếu $h(X) = X$. Cặp $I \times g(I)$ được gọi là cặp Tập mục dữ liệu $\times$ Tập định danh ($IT$-pair). Bốn tính chất quan hệ giữa hai nhánh $I_1 \times g(I_1)$ và $I_2 \times g(I_2)$ xác định việc gộp nhánh, loại bỏ hoặc tạo nhánh mới trong không gian tìm kiếm đóng:
    • Tính chất 1: Nếu $g(I_1) = g(I_2)$, thay thế $I_1$ bằng $I_1 \cup I_2$, loại bỏ $I_2$.
    • Tính chất 2: Nếu $g(I_1) \subset g(I_2)$, thay thế $I_1$ bằng $I_1 \cup I_2$, giữ lại $I_2$.
    • Tính chất 3: Nếu $g(I_1) \supset g(I_2)$, thay thế $I_2$ bằng $I_1 \cup I_2$, giữ lại $I_1$.
    • Tính chất 4: Nếu $g(I_1) \neq g(I_2)$, giữ nguyên cả hai nhánh và thêm nhánh mới $(I_1 \cup I_2) \times (g(I_1) \cap g(I_2))$.
  • Lý thuyết tập mờ và phân hoạch mờ: Thuộc tính định lượng được liên kết với tập mờ $F_{i_k} = {c_{i_k}^1, \dots, c_{i_k}^{h_k}}$. Độ hỗ trợ của tập mờ $\langle X, A \rangle$ được tính bằng toán tử $T$-norm ($\otimes$): $$sup(\langle X, A \rangle) = \frac{1}{|O|} \sum_{t_i \in O} \bigotimes_{x_j \in X} \mu_{c_{x_j}}(t_i[x_j])$$ Hàm thuộc $\mu(x)$ được xây dựng qua các điểm chia $s_i$ và tham số chồng lấp $p$ (%) để xác định biên trên $d_i^+ = s_i - 0.5 \cdot p \cdot (s_i - s_{i-1})$ và biên dưới $d_j^- = s_{j-1} + 0.5 \cdot p \cdot (s_j - s_{j-1})$, đảm bảo tổng giá trị các hàm thuộc tại mỗi điểm luôn bằng 1.
  • Mô hình hồi quy chuyển tiếp trơn (STR): Mô hình phi tuyến dạng: $$y_t = \phi' z_t + \theta' z_t G(\gamma, c, s_t) + u_t$$ Hàm chuyển tiếp logistic bậc một: $G(\gamma, c, s_t) = (1 + \exp{-\gamma(s_t - c)})^{-1}$ với $\gamma > 0$.

2. Phương pháp nghiên cứu thực tế

  • Phương pháp nghiên cứu thuật toán: Thiết kế các cấu trúc dữ liệu và giải thuật tối ưu hóa không gian tìm kiếm dựa trên tính chất đóng của tập mục; phân tích lý thuyết độ phức tạp thời gian và không gian bộ nhớ.
  • Phương pháp thực nghiệm kiểm chứng: Cài đặt thuật toán đối sánh trực tiếp (benchmark testing) giữa thuật toán đề xuất với các thuật toán nền tảng (Apriori-Inverse, CHARM) trên các tập dữ liệu tổng hợp và dữ liệu thực tế; đo lường số lượng tập mục sinh ra và thời gian thực thi (execution time).
  • Phương pháp mô hình hóa kinh tế lượng: Kết hợp kỹ thuật trích xuất tập phổ biến có ràng buộc mục dữ liệu âm ($NC-CHARM$) để lựa chọn các biến trễ/biến tác động phi tuyến, sau đó ước lượng các tham số mô hình LSTR bằng phương pháp phi tuyến bình phương tối thiểu (NLS).

3. Nguồn tư liệu và dữ liệu

  • Cơ sở dữ liệu giao dịch giả định mô phỏng chuẩn: các tập $T5I1000D10K$, $T30I1000D10K$ (trong đó $T$ là kích thước giao dịch trung bình, $I$ là kích thước tập phổ biến trung bình, $D$ là tổng số giao dịch).
  • Cơ sở dữ liệu thực nghiệm chuẩn quốc tế: tập dữ liệu Mushroom từ kho lưu trữ UCI.
  • Dữ liệu thực tế tại Việt Nam: Dữ liệu giao dịch cổ phiếu hàng ngày và chỉ số HNX-Index; dữ liệu thống kê chuỗi thời gian về chỉ số giá tiêu dùng CPI và giá của các nhóm mặt hàng tiêu dùng chính.

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

Chương 1 – PHÁT HIỆN LUẬT KẾT HỢP VÀ LUẬT KẾT HỢP HIẾM

Chương 1 đóng vai trò hệ thống hóa toàn diện nền tảng lý thuyết và tổng quan các công trình liên quan đến luật kết hợp và luật kết hợp hiếm.

Nội dung chương trình bày chi tiết bài toán phát hiện luật kết hợp tổng quát theo quy trình hai bước, cấu trúc dữ liệu và giải thuật của thuật toán Apriori (Hình 1.1, Bảng 1.1), thuật toán tìm tập đóng Galois CHARM (Hình 1.4). Chương phân tích sâu các phương pháp xử lý CSDL định lượng: phương pháp rời rạc hóa truyền thống của Srikant - Agrawal thông qua Bảng 1.2 và Bảng 1.3, chỉ rõ hạn chế về việc phình to kích thước dữ liệu và hiện tượng mất tự nhiên tại các "điểm biên gãy"; từ đó trình bày lý thuyết tập mờ của Kuok và kỹ thuật phân hoạch mờ nhiều chiều của Teuhola (Hình 1.5, công thức 1.6 đến 1.10).

Ở nửa sau của chương, tác giả đi sâu vào bài toán phát hiện luật kết hợp hiếm:

  • Phân tích nguyên nhân thuật toán thông thường thất bại khi tìm luật hiếm do chi phí tìm kiếm bùng nổ khi hạ thấp $minSup$.
  • Khái quát các hướng giải quyết chính: ràng buộc hệ quả cố định (thuật toán Dense-Miner và hệ số cải tiến $Imp$ theo công thức 1.11); đường biên phân chia giữa vùng phổ biến và không phổ biến (thuật toán Apriori-Rare, MRG-Exp, ARIMA, thuật toán Rarity tìm kiếm từ đỉnh không gian).
  • Khảo sát dạng luật Sporadic theo định nghĩa của Koh và cộng sự:
    • Luật Sporadic tuyệt đối: Cả tập mục và từng mục đơn lẻ đều có độ hỗ trợ nhỏ hơn $maxSup$ (công thức 1.12), tìm kiếm bằng thuật toán Apriori-Inverse (Hình 1.6).
    • Luật Sporadic không tuyệt đối: Độ hỗ trợ của tập mục nhỏ hơn $maxSup$ nhưng tồn tại ít nhất một mục đơn có độ hỗ trợ lớn hơn hoặc bằng $maxSup$ (công thức 1.13); phân loại thành 4 nhóm cấu trúc tiền đề/hệ quả; thuật toán MIISR (Hình 1.7) giải quyết nhóm luật có tiền đề phổ biến kết hợp thành không phổ biến và hệ quả hiếm.

Chương kết luận với nhận định về ba khuynh hướng nghiên cứu luật hiếm đang mở: hoàn thiện kỹ thuật tiền xử lý thích hợp, kiểm soát luật nhiễu và đề xuất các độ đo độ thú vị chuyên biệt cho mẫu hiếm.

+---------------------------------------------------------------------------------------------------+
| Bảng 1.1: Diễn giải các kí hiệu sử dụng trong thuật toán Apriori                                 |
+-------------------+-------------------------------------------------------------------------------+
| Kí hiệu           | Ý nghĩa                                                                       |
+-------------------+-------------------------------------------------------------------------------+
| k-itemsets        | Tập k - mục dữ liệu                                                           |
| Lk                | Tập các k - tập dữ liệu phổ biến (gồm 2 trường: tập dữ liệu và độ hỗ trợ)     |
| Ck                | Tập các k - tập dữ liệu ứng cử viên (gồm 2 trường: tập dữ liệu và độ hỗ trợ)  |
+-------------------+-------------------------------------------------------------------------------+

Chương 2 - PHÁT HIỆN LUẬT KẾT HỢP HIẾM TRÊN CƠ SỞ DỮ LIỆU TÁC VỤ

Chương 2 trình bày các đóng góp lý thuyết và thuật toán cốt lõi của tác giả dành cho CSDL tác vụ nhị phân, giải quyết ba bài toán cụ thể:

1. Luật kết hợp Sporadic tuyệt đối hai ngưỡng

Tác giả đề xuất mở rộng mô hình Sporadic tuyệt đối bằng cách bổ sung ngưỡng hỗ trợ cận dưới $minSup$ ($minSup < maxSup$), loại bỏ việc phụ thuộc vào giá trị ngầm định $minAS$ của Apriori-Inverse. Định nghĩa toán học (công thức 2.1): $$\begin{cases} conf(A \to B) \ge minConf \ minSup \le sup(A \cup B) < maxSup \ \forall x \in A \cup B, sup(x) < maxSup \end{cases}$$ Thay vì sinh toàn bộ tập hiếm, tác giả đề xuất tiếp cận không gian tập Sporadic tuyệt đối hai ngưỡng đóng dựa trên kết nối Galois. Tác giả chứng minh hai tính chất nền tảng:

  • Tính chất 2.1: Tập tất cả các tập hiếm cực đại bằng tập tất cả các tập hiếm đóng cực đại.
  • Tính chất 2.2: Các luật kết hợp hiếm sinh ra từ tập hiếm và từ tập hiếm cực đại là đồng nhất.

Từ đó, tác giả xây dựng thuật toán MCPSI (Mining Closed Perfectly Sporadic Itemsets, Hình 2.1). Không gian tìm kiếm được giới hạn trong cây tiền tố của các $IT$-pair (Hình 2.2). Kết quả thực nghiệm đối sánh giữa MCPSI và Apriori-Inverse trên các CSDL giả định (Bảng 2.1, 2.2, Hình 2.3), tập $T5I1000D10K$ (Bảng 2.3) và các CSDL thực tế (Bảng 2.4, Hình 2.4) khẳng định: trong tất cả các trường hợp, MCPSI tiêu tốn thời gian thực thi ít hơn rõ rệt và số lượng tập đóng tìm được luôn nhỏ hơn số lượng tập do Apriori-Inverse sinh ra, giúp triệt tiêu các luật hiếm dư thừa.

2. Luật kết hợp Sporadic không tuyệt đối hai ngưỡng

Mở rộng cho trường hợp tồn tại mục dữ liệu có độ hỗ trợ $\ge maxSup$. Tác giả xây dựng thuật toán MCISI (Mining Closed Imperfectly Sporadic Itemsets, Hình 2.5) để tìm kiếm các tập Sporadic không tuyệt đối hai ngưỡng đóng. Thuật toán kết hợp duyệt nhánh và áp dụng các tính chất đóng Galois để cắt tỉa không gian tìm kiếm. Thực nghiệm trên CSDL $T5I1000D10K$ (Bảng 2.5), CSDL giả định (Bảng 2.6), CSDL thực và tập Mushroom với các ngưỡng $minSup = 0,1$ và $maxSup = 0,5$ (Bảng 2.7 - 2.10, Hình 2.6 - 2.7) cho thấy thuật toán vận hành ổn định và kiểm soát tốt kích thước tập kết quả.

3. Luật kết hợp với ràng buộc mục dữ liệu âm

Tác giả nghiên cứu bài toán tìm tập phổ biến có chứa các mục dữ liệu phủ định ($\neg i$), biểu thị mối quan hệ khi một mặt hàng/sự kiện vắng mặt thì kéo theo sự xuất hiện của mục khác. Tác giả đề xuất thuật toán NC-CHARM (Negative Constrains - Closed Association Rules Mining, Hình 2.8). Thuật toán áp dụng cơ chế cây tìm kiếm tập phổ biến có ràng buộc âm (Hình 2.9). Dữ liệu minh họa được kiểm chứng qua Bảng 2.11, Bảng 2.12 và kết quả thực nghiệm trên tệp $T30I1000D10K$ được tổng hợp tại Bảng 2.13 và Hình 2.10, chứng minh hiệu năng cắt tỉa vượt trội của việc tích hợp toán tử Galois trên mẫu âm.

Chương 3 - PHÁT HIỆN LUẬT KẾT HỢP HIẾM TRÊN CƠ SỞ DỮ LIỆU ĐỊNH LƯỢNG

Chương 3 giải quyết bài toán phát hiện luật kết hợp hiếm trên các CSDL chứa thuộc tính liên tục và phân loại bằng cách kết hợp lý thuyết tập mờ nhằm loại bỏ hiện tượng "điểm biên gãy".

1. Luật kết hợp Sporadic tuyệt đối hai ngưỡng mờ

Định nghĩa tập Sporadic tuyệt đối hai ngưỡng mờ trên CSDL mờ: độ hỗ trợ mờ của tập thỏa mãn $minSup \le sup(\langle X, A \rangle) < maxSup$ và mọi thuộc tính mờ đơn lẻ đều có độ hỗ trợ mờ $< maxSup$. Tác giả đề xuất thuật toán MFPSI (Mining Fuzzy Perfectly Sporadic Itemsets, Hình 3.1) được phát triển theo tư tưởng duyệt mức của thuật toán Apriori nhưng tích hợp toán tử $T$-norm mờ. Quá trình tính toán được minh họa chi tiết qua một CSDL mờ mẫu (Bảng 3.1), bảng độ hỗ trợ thuộc tính đơn (Bảng 3.2), bảng độ hỗ trợ 2-thuộc tính mờ (Bảng 3.3). Bảng 3.4 ghi nhận kết quả thực hiện thử nghiệm của MFPSI khi thay đổi các ngưỡng mờ.

2. Luật kết hợp Sporadic không tuyệt đối hai ngưỡng mờ

Tác giả đưa ra khái niệm tập Sporadic không tuyệt đối hai ngưỡng mờ (chứa ít nhất một thuộc tính mờ có độ hỗ trợ $\ge maxSup$ trong khi toàn bộ tập mờ có độ hỗ trợ nằm trong khoảng $[minSup, maxSup)$). Tác giả thiết kế thuật toán MFISI (Mining Fuzzy Imperfectly Sporadic Itemsets, Hình 3.2). Thuật toán kết hợp tư tưởng của MCISI để duyệt và kiểm tra điều kiện mờ. Dữ liệu tính toán từng bước được minh họa qua các Bảng 3.5, 3.6, cấu trúc tập tìm được tại Node thứ nhất (Bảng 3.7) và kết quả thử nghiệm tổng hợp trên nhiều trường hợp tham số khác nhau (Hình 3.3 đến 3.6, Bảng 3.8). Kết quả chứng minh thuật toán xác định chính xác các mẫu hiếm mờ phức hợp mà phương pháp nhị phân hóa thông thường bỏ sót.

Chương 4 - ỨNG DỤNG LUẬT KẾT HỢP MẪU ÂM VÀ MÔ HÌNH HỒI QUY CHUYỂN TIẾP TRƠN TRONG PHÂN TÍCH VÀ DỰ BÁO KINH TẾ

Chương 4 hiện thực hóa tính ứng dụng thực tiễn của luận án bằng việc đề xuất một quy trình lai ghép mới: sử dụng thuật toán phát hiện luật kết hợp có ràng buộc mục dữ liệu âm để sàng lọc và xác định các mối quan hệ phi tuyến tiềm ẩn giữa các biến kinh tế, sau đó đưa các biến này vào mô hình hồi quy chuyển tiếp trơn logistic (LSTR) để tiến hành dự báo.

1. Cơ sở mô hình hồi quy chuyển tiếp trơn (STR)

Tác giả trình bày lý thuyết phân tích hồi quy phi tuyến, cấu trúc mô hình hồi quy chuyển tiếp trơn logistic (LSTR), các bước kiểm định tính phi tuyến (sử dụng khai triển Taylor để kiểm định giả thuyết tuyến tính) và quy trình ước lượng tham số mô hình thông qua thuật toán tối ưu hóa phi tuyến.

2. Xây dựng mô hình phân tích và dự báo chỉ số chứng khoán

  • Dữ liệu: Sử dụng dữ liệu chuỗi thời gian giao dịch của các mã cổ phiếu niêm yết trên sàn HNX và chỉ số HNX-Index (Hình 4.1).
  • Phát hiện mối quan hệ: Áp dụng giải thuật khai phá mẫu âm để phát hiện mối liên hệ nghịch chiều hoặc các tương tác hiếm giữa biến động giá của từng nhóm cổ phiếu cụ thể đối với sự sụt giảm hoặc tăng trưởng của chỉ số chứng khoán.
  • Kết quả ước lượng: Các tham số của mô hình LSTR được ước lượng thành công (Hình 4.2).
  • Đánh giá thực nghiệm: Bảng 4.1 và Đồ thị Hình 4.3 đối sánh giá trị chỉ số HNX tính toán theo mô hình xây dựng với dữ liệu chỉ số thực tế trên thị trường, chứng minh độ tin cậy và mức độ bám sát xu thế rất cao của mô hình dự báo đề xuất.

3. Xây dựng mô hình dự báo chỉ số giá tiêu dùng (CPI)

  • Dữ liệu: Thu thập chuỗi số liệu định kỳ về biến động giá của các mặt hàng/nhóm mặt hàng tiêu dùng trọng yếu cấu thành rổ hàng hóa và chỉ số CPI tương ứng (Hình 4.4).
  • Phát hiện mối quan hệ: Sử dụng luật kết hợp mẫu âm để phát hiện tương tác giữa sự biến động ngược chiều của giá một số nhóm hàng hóa đầu vào đối với chỉ số CPI chung.
  • Ước lượng và kết quả: Tác giả ước lượng các hệ số hồi quy chuyển tiếp trơn (Hình 4.5). Bảng 4.2 tổng hợp chi tiết chỉ số CPI được tính theo mô hình xây dựng đối chiếu với số liệu thống kê thực tế, cho thấy sai số dự báo được kiểm soát ở mức nhỏ, phản ánh tốt các bước chuyển trạng thái trơn của nền kinh tế.
+---------------------------------------------------------------------------------------------------+
| Bảng tổng hợp các thuật toán đề xuất chính trong luận án                                         |
+-----------+----------------------+--------------------+-------------------------------------------+
| Thuật toán| Loại cơ sở dữ liệu   | Lớp luật mục tiêu  | Đặc trưng kỹ thuật chính                  |
+-----------+----------------------+--------------------+-------------------------------------------+
| MCPSI     | CSDL tác vụ nhị phân | Sporadic tuyệt đối | Hai ngưỡng, không gian tập đóng Galois    |
| MCISI     | CSDL tác vụ nhị phân | Sporadic không     | Hai ngưỡng, mở rộng kiểm tra mục phổ biến |
|           |                      | tuyệt đối          | và không phổ biến kết hợp                 |
| NC-CHARM  | CSDL tác vụ nhị phân | Mẫu có ràng buộc âm| Kết hợp toán tử phủ định và tập đóng CHARM|
| MFPSI     | CSDL định lượng      | Sporadic tuyệt đối | Lý thuyết tập mờ, T-norm, duyệt mức       |
|           |                      | mờ                 | Apriori                                   |
| MFISI     | CSDL định lượng      | Sporadic không     | Khung thuật toán MCISI kết hợp với các    |
|           |                      | tuyệt đối mờ       | hàm thuộc phân hoạch mờ                   |
+-----------+----------------------+--------------------+-------------------------------------------+

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

Luận án đã đạt được các đóng góp học thuật và thực tiễn cụ thể như sau:

  • Đóng góp về lý luận và thuật toán:

    1. Đề xuất cách tiếp cận không gian tập đóng cho luật hiếm: Khác với các nghiên cứu trước đây (như Apriori-Inverse, ARIMA) vốn duyệt trên toàn bộ không gian tập không phổ biến, luận án là công trình đầu tiên đề xuất hướng tiếp cận tìm kiếm tập không phổ biến đóng dựa trên dàn Galois và toán tử đóng. Tiếp cận này chứng minh tập các tập hiếm cực đại bằng tập các tập hiếm đóng cực đại, từ đó giảm đáng kể kích thước không gian tìm kiếm và loại bỏ các luật hiếm dư thừa.
    2. Phát triển ba thuật toán mới trên CSDL tác vụ:
      • Thuật toán MCPSI: Khai phá tập Sporadic tuyệt đối hai ngưỡng đóng, khắc phục việc phải định nghĩa ngưỡng ngầm định $minAS$.
      • Thuật toán MCISI: Khai phá tập Sporadic không tuyệt đối hai ngưỡng đóng, bao phủ các trường hợp kết hợp giữa mục phổ biến và mục hiếm.
      • Thuật toán NC-CHARM: Khai phá tập phổ biến đóng với ràng buộc mục dữ liệu âm.
    3. Mở rộng lý thuyết phát hiện luật hiếm trên CSDL định lượng: Luận án đã giải quyết hạn chế của các nghiên cứu trước (chỉ tìm luật hiếm thuần túy trên thuộc tính không phổ biến) bằng cách kết hợp lý thuyết tập mờ và phân hoạch mờ đa chiều để đề xuất:
      • Khái niệm luật kết hợp Sporadic tuyệt đối hai ngưỡng mờ và thuật toán MFPSI.
      • Khái niệm luật kết hợp Sporadic không tuyệt đối hai ngưỡng mờ và thuật toán MFISI. Hai mô hình này xử lý triệt để hiện tượng "điểm biên gãy" khi rời rạc hóa dữ liệu số liên tục.

  • Đóng góp về thực tiễn và giải pháp đề xuất:

    • Đề xuất quy trình phối hợp liên ngành giữa kỹ thuật khai phá mẫu kết hợp âm trong Công nghệ thông tin và mô hình hồi quy phi tuyến chuyển tiếp trơn LSTR trong Kinh tế lượng.
    • Xây dựng thành công hai mô hình thực nghiệm phân tích và dự báo: mô hình dự báo biến động chỉ số chứng khoán HNX-Index và mô hình dự báo chỉ số giá tiêu dùng CPI tại Việt Nam. Kết quả kiểm định đối chiếu số liệu tính toán với thực tế cho thấy sai số thấp, phản ánh chính xác các biến động thị trường so với mô hình tuyến tính cổ điển.

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

Dựa trên nội dung văn bản luận án trình bày:

  • Hạn chế:

    • Luận án mới chỉ tập trung giải quyết chuyên sâu Giai đoạn 1 của bài toán khai phá luật kết hợp hiếm (tìm kiếm các tập mục dữ liệu hiếm tương ứng), chưa đi sâu tối ưu hóa toàn diện Giai đoạn 2 (thuật toán sinh luật chi tiết và các độ đo lọc luật sau khi có tập mục).
    • Khi kích thước CSDL mở rộng lên quy mô cực lớn hoặc khi người dùng thiết lập ngưỡng độ hỗ trợ cận dưới $minSup$ cực kỳ nhỏ sát 0, số lượng tập ứng viên trung gian vẫn đòi hỏi chi phí lưu trữ bộ nhớ đáng kể.
    • Việc thiết lập các tham số ngưỡng ($minSup, maxSup, minConf$, tham số phân hoạch mờ $p$) vẫn phụ thuộc chủ yếu vào sự am hiểu dữ liệu của người dùng, chưa có cơ chế tự động tối ưu tham số.

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

    • Phát triển các cấu trúc dữ liệu nén trong bộ nhớ (như biến thể cây tiền tố FP-Tree) kết hợp với kỹ thuật song song hóa để tăng tốc độ khai phá trên CSDL quy mô siêu lớn.
    • Nghiên cứu các độ đo đánh giá độ thú vị chuyên biệt cho luật hiếm nhằm tự động loại bỏ luật nhiễu ở Giai đoạn 2.
    • Mở rộng ứng dụng mô hình kết hợp luật mẫu âm và hồi quy chuyển tiếp trơn sang các bài toán kinh tế vĩ mô phức tạp khác như dự báo chỉ số sản xuất công nghiệp, tỷ giá hối đoái hoặc cảnh báo rủi ro tài chính ngân hàng.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên khảo có giá trị học thuật trong lĩnh vực Khai phá dữ liệu và Hệ thống thông tin:

  • Đối với nghiên cứu sinh và học viên cao học chuyên ngành Khoa học máy tính, Hệ thống thông tin:

    • Cung cấp tài liệu tổng quan toàn diện về lý thuyết khai phá luật kết hợp, cấu trúc dàn Galois, toán tử đóng và các thuật toán kinh điển (Apriori, CHARM, Apriori-Inverse).
    • Cung cấp phương pháp luận toán học chặt chẽ trong việc định nghĩa bài toán, chứng minh tính chất đóng và thiết kế giải thuật tối ưu hóa không gian tìm kiếm (Chương 2 và Chương 3).

  • Đối với giảng viên và các nhà nghiên cứu:

    • Cung cấp khung phân tích hoàn chỉnh về việc tích hợp lý thuyết tập mờ để giải quyết bài toán "điểm biên gãy" trên dữ liệu định lượng số liên tục.
    • Là tài liệu tham khảo hữu ích cho các bài giảng chuyên đề về Khai phá dữ liệu nâng cao (Advanced Data Mining).

  • Đối với chuyên viên phân tích tài chính, kinh tế lượng và người làm chính sách:

    • Cung cấp giải pháp kỹ thuật cụ thể (Chương 4) trong việc sử dụng luật kết hợp mẫu âm để sàng lọc biến tác động phi tuyến trước khi đưa vào mô hình hồi quy kinh tế lượng.
    • Quy trình dự báo CPI và chỉ số chứng khoán trình bày trong luận án có thể chuyển giao, cài đặt trực tiếp vào các hệ thống hỗ trợ ra quyết định phân tích thị trường thực tế.

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

1. Điểm khác biệt căn bản giữa thuật toán MCPSI của luận án và thuật toán Apriori-Inverse của Y. Koh là gì?
Trả lời: Thuật toán Apriori-Inverse tìm kiếm tất cả các tập Sporadic tuyệt đối theo chiến lược duyệt theo chiều rộng kiểu Apriori và sử dụng một ngưỡng ngầm định $minAS$. Ngược lại, thuật toán MCPSI của luận án đưa vào hai ngưỡng tường minh ($minSup$ và $maxSup$), đồng thời áp dụng cấu trúc kết nối Galois để chỉ tìm các tập Sporadic tuyệt đối đóng. Nhờ vậy, MCPSI có thời gian thực thi nhanh hơn rõ rệt và loại bỏ được các tập mục cũng như luật hiếm dư thừa.

2. Bốn tính chất quan hệ của các cặp $IT$-pair trong thuật toán CHARM được luận án kế thừa như thế nào?
Trả lời: Luận án kế thừa 4 tính chất quan hệ giữa hai nhánh $I_1 \times g(I_1)$ và $I_2 \times g(I_2)$ dựa trên tập giao tác vụ $g(I)$: (1) Nếu $g(I_1) = g(I_2)$, gộp thành $I_1 \cup I_2$ và loại bỏ $I_2$; (2) Nếu $g(I_1) \subset g(I_2)$, thay $I_1$ bằng $I_1 \cup I_2$ và giữ $I_2$; (3) Nếu $g(I_1) \supset g(I_2)$, thay $I_2$ bằng $I_1 \cup I_2$ và giữ $I_1$; (4) Nếu $g(I_1) \neq g(I_2)$, tạo nhánh mới $(I_1 \cup I_2) \times (g(I_1) \cap g(I_2))$. Cơ chế này giúp thuật toán MCPSI duyệt không gian theo chiều sâu và cắt tỉa các tập không đóng.

3. Tại sao luận án phải sử dụng lý thuyết tập mờ khi khai phá luật hiếm trên CSDL định lượng?
Trả lời: Khi chuyển đổi CSDL định lượng sang dạng tác vụ bằng phương pháp phân khoảng nhị phân thông thường của Srikant và Agrawal, hệ thống gặp hiện tượng "điểm biên gãy" (giá trị rất gần nhau như 59 tuổi và 60 tuổi bị chia vào hai khoảng đối nghịch nhau) và làm giảm độ hỗ trợ của các khoảng đơn lẻ. Lý thuyết tập mờ và kỹ thuật phân hoạch mờ của Teuhola gán cho mỗi giá trị một độ thuộc $\mu \in [0, 1]$, giúp biểu diễn ranh giới mềm dẻo và tính toán độ hỗ trợ chính xác thông qua toán tử $T$-norm.

4. Mô hình dự báo trong Chương 4 kết hợp luật mẫu âm và hồi quy chuyển tiếp trơn như thế nào?
Trả lời: Thuật toán NC-CHARM được sử dụng ở bước tiền xử lý để phát hiện các mối quan hệ kết hợp mẫu âm (nghịch chiều hoặc sự vắng mặt của thuộc tính này dẫn đến sự xuất hiện của thuộc tính khác giữa giá cổ phiếu hoặc giá hàng hóa). Các biến có mối quan hệ phi tuyến này được chọn làm biến chuyển tiếp ($s_t$) và biến giải thích ($z_t$) trong mô hình hồi quy chuyển tiếp trơn logistic LSTR để ước lượng và dự báo các chỉ số HNX-Index và CPI.

5. Luận án giải quyết hai giai đoạn của bài toán khai phá luật kết hợp hiếm như thế nào?
Trả lời: Bài toán gồm hai giai đoạn: Giai đoạn 1 là tìm tất cả các tập mục dữ liệu hiếm thỏa mãn ngưỡng hỗ trợ; Giai đoạn 2 là sinh các luật hiếm thỏa mãn độ tin cậy $minConf$. Luận án tập trung giải quyết Giai đoạn 1 vì đây là giai đoạn có độ phức tạp tính toán lớn nhất ($O(2^{|I|})$); khi tìm được đầy đủ các tập mục hiếm đóng hoặc tập mờ và độ hỗ trợ của chúng, Giai đoạn 2 được thực hiện thuận lợi và trực tiếp.

Kết luận

Luận án tiến sĩ của tác giả Cù Thu Thủy đã giải quyết có hệ thống bài toán phát hiện luật kết hợp hiếm trên cả hai môi trường cơ sở dữ liệu tác vụ và cơ sở dữ liệu định lượng. Bằng việc tích hợp cấu trúc không gian tập đóng Galois và lý thuyết tập mờ, tác giả đã đề xuất năm thuật toán mới (MCPSI, MCISI, NC-CHARM, MFPSI, MFISI), giúp nâng cao hiệu năng tính toán và triệt tiêu đáng kể các luật hiếm dư thừa. Đồng thời, nghiên cứu đã chứng minh tính ứng dụng thực tiễn của các mô hình lý thuyết thông qua việc kết hợp mẫu kết hợp âm với mô hình hồi quy chuyển tiếp trơn LSTR để dự báo hiệu quả chỉ số chứng khoán và chỉ số giá tiêu dùng tại Việt Nam.