Tổng quan luận án

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

Sự gia tăng quy mô của các hệ thống cơ sở dữ liệu và kho thông tin quản lý đặt ra yêu cầu khai thác các quy luật tiềm ẩn phục vụ quản lý, kinh tế - xã hội và trí tuệ nhân tạo. Trong khai phá dữ liệu, bài toán khai phá luật kết hợp (Association Rule Mining - AR) được khởi xướng từ mô hình dữ liệu nhị phân (giao dịch giỏ hàng), sau đó mở rộng sang các cơ sở dữ liệu có thuộc tính định lượng và số thực. Để xử lý các thuộc tính định lượng, cách tiếp cận thông thường là rời rạc hóa miền giá trị thành các khoảng rời rạc; tuy nhiên, phương pháp này gặp phải hiện tượng "điểm biên gãy" (sharp boundary problem).

Lý thuyết tập mờ được đưa vào nhằm làm trơn các biên và mô tả tri thức dưới dạng ngôn ngữ tự nhiên thông qua các luật kết hợp mờ có dạng "Nếu $X$ là $A$ thì $Y$ là $B$". Dẫu vậy, phương pháp tiếp cận dựa trên lý thuyết tập mờ truyền thống bộc lộ những khoảng trống nghiên cứu kỹ thuật:

  • Quá trình thiết kế các hàm thuộc (Membership Functions - MF) và gán nhãn ngôn ngữ thường dựa trên trực quan, tri thức chủ quan của chuyên gia, thiếu tính ràng buộc cấu trúc ngữ nghĩa giữa các từ ngôn ngữ, dẫn đến các hàm thuộc có thể không tương thích với dữ liệu và làm giảm tính tin cậy của tập luật trích xuất.
  • Khi sử dụng giải thuật di truyền (Genetic Algorithm - GA) để tối ưu hóa hàm thuộc trong cách tiếp cận tập mờ, điểm xuất phát ban đầu chưa tốt khiến các hàm thuộc thu được dễ bị chồng lấn cao và ngữ nghĩa của luật chưa tối ưu.
  • Về mặt hiệu năng, khai phá luật kết hợp có độ phức tạp hàm mũ do phải quét cơ sở dữ liệu nhiều lần để kiểm tra các tập mục phổ biến. Các giải pháp nén dữ liệu giao dịch trước đây (tiêu biểu như thuật toán M2TQT) chỉ giới hạn trên cơ sở dữ liệu nhị phân mà chưa mở rộng hiệu quả cho cơ sở dữ liệu giao dịch mờ.

Nhằm giải quyết các khoảng trống này, luận án áp dụng lý thuyết Đại số gia tử (ĐSGT) để mô hình hóa ngữ nghĩa tính toán của các từ ngôn ngữ, thiết lập các phân hoạch mờ có cấu trúc chặt chẽ, kết hợp giải thuật di truyền để tối ưu tham số và xây dựng thuật toán nén cơ sở dữ liệu giao dịch mờ.

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

Luận án xác định các mục tiêu và nhiệm vụ nghiên cứu cụ thể như sau:

  1. Nghiên cứu phương pháp luận phát hiện tri thức dạng luật mờ biểu diễn bằng thông tin ngôn ngữ từ cơ sở dữ liệu số nhằm trích xuất các mối quan hệ ngữ nghĩa phục vụ quản lý và làm cơ sở cho lập luận mờ.
  2. Đề xuất giải pháp nén dữ liệu giao dịch mờ thông qua việc xác định quan hệ khoảng cách giữa các giao dịch mờ, giúp giảm kích thước cơ sở dữ liệu đầu vào và giảm thời gian quét dữ liệu khi khai phá luật kết hợp.
  3. Nghiên cứu phương pháp xây dựng phân hoạch mờ cho các thuộc tính định lượng dựa trên cấu trúc Đại số gia tử dưới hai hình thức biểu diễn: đơn thể hạt (single-granularity) và đa thể hạt (multi-granularity).
  4. Xây dựng giải thuật tối ưu hóa các tham số mờ của cấu trúc Đại số gia tử bằng giải thuật di truyền mô hình CHC nhằm tìm kiếm hệ hàm thuộc tối ưu, nâng cao chất lượng ngữ nghĩa và độ thú vị của các luật kết hợp mờ.

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

  • Đối tượng nghiên cứu: Cơ sở dữ liệu chứa các thuộc tính định lượng và hạng mục; các mô hình biểu diễn tri thức luật kết hợp mờ; cấu trúc toán học của Đại số gia tử tuyến tính; các độ đo ngữ nghĩa (độ đo tính mờ, hàm định lượng ngữ nghĩa, khoảng tính mờ); giải thuật nén dữ liệu giao dịch và giải thuật di truyền CHC.
  • Phạm vi dữ liệu thực nghiệm: Dữ liệu thực nghiệm được kiểm chứng trên các tập dữ liệu thực tế và chuẩn hóa, bao gồm:
    • Cơ sở dữ liệu điều tra dân số Hoa Kỳ năm 1995 (FAM95) với 63.565 bản ghi gồm 5 thuộc tính được chọn: Tuổi (Age), Giờ làm việc (Hours), Thu nhập gia đình (IncFam), Thu nhập chủ hộ (IncHead), và Giới tính (Sex).
    • Cơ sở dữ liệu y tế STULONG với 1.417 bản ghi gồm 5 thuộc tính số nguyên $A_1, A_2, A_3, A_4, A_5$ tương ứng các miền giá trị $[-1, 199]$, $[-1, 133]$, $[90, 225]$, $[50, 145]$, $[-1, 530]$.
    • Các tập dữ liệu đối sánh khác trong đánh giá độ thú vị và tập phổ biến: Pollution, Basketball, Quake, Stock.

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 đây

Tác giả đã hệ thống hóa các công trình nghiên cứu trong và ngoài nước theo các nhóm hướng nghiên cứu chính:

  1. Khai phá luật kết hợp nhị phân và mở rộng định lượng:

    • Agrawal và cộng sự (1994) [21] đề xuất bài toán khai phá luật kết hợp cổ điển và thuật toán Apriori trên cơ sở dữ liệu giao dịch nhị phân với hai độ đo cốt lõi là Độ hỗ trợ (Support) và Độ tin cậy (Confidence).
    • Srikant và Agrawal [8] nghiên cứu mở rộng sang cơ sở dữ liệu định lượng bằng phương pháp chia miền giá trị thành các khoảng rời rạc, làm nảy sinh hạn chế về ranh giới cứng giữa các khoảng.

  2. Khai phá luật kết hợp mờ (Fuzzy Association Rules):

    • Kuok, Fu, Wong [29, 30] cùng các công trình [31, 57] đề xuất khai phá luật kết hợp mờ nhằm xử lý dữ liệu số, trong đó người dùng hoặc chuyên gia phải cung cấp trước các tập mờ và hàm thuộc.
    • Các thuật toán mở rộng tiếp theo [27, 59, 61, 65] tiếp tục sử dụng hàm thuộc định sẵn, mang tính chủ quan và khó áp dụng linh hoạt trong thực tế.

  3. Tối ưu hóa và tìm kiếm hàm thuộc từ dữ liệu:

    • Các công trình của Tzung-Pei Hong và cộng sự (2004 [83], 2008 [42], 2016 [46], 2018 [60]), Herrera và cộng sự (2009 [53], 2015 [22]), Harikesh Bahadur Yadav và cộng sự (2015) [14], Aashna Agarwal và cộng sự (2016) [7], Hemant Kumar Soni và cộng sự (2016) [38], Harihar Kalia và cộng sự (2016) [74], Umesh Kumar Patel và cộng sự (2016) [76], Umit Can và cộng sự (2017) [9], Archana Gupta và cộng sự (2019) [75] đã sử dụng giải thuật di truyền (GA) để tìm kiếm các hàm thuộc trực tiếp từ dữ liệu giao dịch. Tuy nhiên, cách tiếp cận thuần túy theo tập mờ khiến cấu trúc ban đầu chưa chặt chẽ, hàm thuộc sau tối ưu dễ gặp hiện tượng phân bố lệch hoặc độ chồng lấn không hợp lý.

  4. Ứng dụng Đại số gia tử vào khai phá dữ liệu mờ:

    • Lý thuyết Đại số gia tử do N. C. Ho và Wechler đề xuất (1990, 1992) [19, 49] mô hình hóa miền ngôn ngữ dựa trên quan hệ thứ tự tự nhiên.
    • Nguyễn Công Hào và cộng sự (2012) [2] xem miền trị thuộc tính như một cấu trúc ĐSGT và ánh xạ mỗi giá trị vào một phần tử ĐSGT thông qua hàm ngược, phương pháp này làm mất mát thông tin.
    • Nguyễn Nam Tiến và cộng sự (2012) [3] khắc phục bằng cách tính khoảng cách từ giá trị thực tới giá trị định lượng ngữ nghĩa của hai phần tử ĐSGT lân cận, lưu trữ một cặp giá trị thay vì một giá trị đơn lẻ.

  5. Nén cơ sở dữ liệu giao dịch để tăng tốc độ khai phá:

    • Jia-Yu Dai và cộng sự (2008) [18] đề xuất thuật toán M2TQT nén cơ sở dữ liệu nhị phân bằng cách gộp các giao dịch có quan hệ gần nhau.
    • Chien-Min Lin (2013) [5] và Chun-Wei Lin và cộng sự (2009) [34] phát triển giải pháp nén dữ liệu giao dịch rõ và mờ lên cấu trúc cây FP-Tree.

  6. Biểu diễn dữ liệu đa thể hạt (Multi-granularity):

    • Các công trình nghiên cứu sử dụng hàm thuộc đa thể hạt trong khai phá tri thức [37, 66, 67, 68, 82, 84] mở ra khả năng biểu diễn tri thức ở nhiều mức trừu tượng khác nhau.

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

Luận án định vị trọng tâm giải quyết hai vấn đề kỹ thuật chưa được xử lý triệt để:

  • Thứ nhất, phát triển thuật toán nén cơ sở dữ liệu giao dịch mờ dựa trên quan hệ khoảng cách mờ kết hợp Bảng định lượng, khắc phục giới hạn của thuật toán M2TQT vốn chỉ áp dụng cho dữ liệu nhị phân.
  • Thứ hai, khắc phục tính chủ quan của tập mờ truyền thống bằng cách sử dụng cấu trúc toán học của ĐSGT để xây dựng các phân hoạch mờ đơn thể hạt và đa thể hạt có tính chất phân hoạch mạnh, sau đó dùng giải thuật GA mô hình CHC để tối ưu hóa bộ tham số mờ, tạo ra các luật kết hợp ngôn ngữ có ngữ nghĩa chặt chẽ và độ thú vị cao.

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

Khung lý thuyết và khái niệm sử dụng

Luận án xây dựng trên ba trụ cột lý thuyết chính:

  1. Lý thuyết tập mờ và biến ngôn ngữ:

    • Tập mờ $A$ trên vũ trụ $U$ xác định bởi hàm thuộc $\mu_A(x): U \to [0, 1]$ (Zadeh, 1965 [40]). Các dạng hàm thuộc chính gồm hàm tam giác và hình thang.
    • Biến ngôn ngữ định nghĩa bởi bộ 5 thành phần $(X, T(X), U, R, M)$ theo L.A. Zadeh [13].
    • Phân hoạch mờ của khoảng $U = [a, b]$ gồm $m$ tập mờ ${A_1, \dots, A_m}$ với các điểm mốc $p_1, \dots, p_m$. Nếu $\sum_{k=1}^m \mu_{A_k}(x) = 1, \forall x \in U$, phân hoạch được gọi là phân hoạch mờ mạnh (strong fuzzy partition) [36].

  2. Lý thuyết Đại số gia tử (Hedge Algebras - HA):

    • Một ĐSGT tuyến tính là bộ $AX = (X, G, H, \le)$, trong đó $X$ là tập các giá trị ngôn ngữ (hạng từ), $G = {c^-, W, c^+}$ hoặc ${0, W, 1}$ là tập phần tử sinh, $H = H^- \cup H^+$ là tập các gia tử (gia tử âm làm giảm ngữ nghĩa, gia tử dương làm tăng ngữ nghĩa), $\le$ là quan hệ thứ tự cảm sinh ngữ nghĩa [19, 49]. ĐSGT tuyến tính đầy đủ bổ sung hai gia tử giới hạn $\sigma, \phi$, ký hiệu $AX^* = (X, G, H, \sigma, \phi, \le)$.
    • Độ đo tính mờ $fm(x)$ của hạng từ và độ đo tính mờ $\mu(h)$ của gia tử $h \in H$ thỏa mãn điều kiện đầy đủ: $fm(c^-) + fm(c^+) = 1$ và $\sum_{h \in H} fm(hu) = fm(u)$. Tỷ số $\mu(h) = \frac{fm(hx)}{fm(x)}$ không phụ thuộc vào $x$.
    • Hàm định lượng ngữ nghĩa (Semantically Quantifying Mapping - SQM) $v: X \to [0, 1]$ ánh xạ mỗi từ ngôn ngữ thành một giá trị số thực trên đoạn $[0, 1]$ bảo toàn trật tự ngữ nghĩa [25].
    • Khoảng tính mờ (fuzziness interval) $\Im_{fm}(x)$ có độ dài đúng bằng $fm(x)$, cung cấp cơ chế phân chia không gian ngữ nghĩa một cách tự nhiên.

  3. Lý thuyết khai phá luật kết hợp và giải thuật di truyền:

    • Cấu trúc luật $X \to Y$ với $X, Y \subset I, X \cap Y = \emptyset$. Các độ đo chuẩn: $$\text{Support}(X \to Y) = \frac{|T(X \cup Y)|}{|D|}, \quad \text{Confidence}(X \to Y) = \frac{|T(X \cup Y)|}{|T(X)|}, \quad \text{Lift}(X \to Y) = \frac{\text{Supp}(X \cup Y)}{\text{Supp}(X) \times \text{Supp}(Y)}$$
    • Độ hỗ trợ mờ $fs(\langle Z, C \rangle)$ và độ tin cậy mờ $FC$ của tập thuộc tính mờ $\langle Z, C \rangle$ với $Z = X \cup Y, C = A \cup B$: $$fs(\langle Z, C \rangle) = \frac{\sum_{i=1}^n \prod_{j=1}^m t_i[(x_j, a_j)]}{n}$$ $$FC((X, A) \to (Y, B)) = \frac{fs(\langle Z, C \rangle)}{fs(\langle X, A \rangle)}$$
    • Giải thuật di truyền mô hình CHC (Eshelman, 1991 [10]) áp dụng chọn lọc dựa trên quần thể (Population-based Selection), cơ chế phòng tránh giao phối cận huyết dựa trên khoảng cách Hamming và khởi tạo lại quần thể thay cho toán tử đột biến truyền thống.

Phương pháp nghiên cứu và quy trình kỹ thuật

Phương pháp nghiên cứu thuộc hướng định lượng và kỹ thuật thuật toán:

  • Mờ hóa dữ liệu dựa trên ĐSGT: Mỗi thuộc tính định lượng được chuẩn hóa về đoạn $[0, 1]$. Dựa trên các giá trị định lượng ngữ nghĩa $v(s_j)$ của các phần tử trong ĐSGT, một giá trị dữ liệu $d_i^x$ nằm giữa hai phần tử lân cận sẽ nhận hai giá trị độ thuộc thông qua khoảng cách: $\mu_{s_j}(d_i^x) = 1 - |v(s_j) - d_i^x|$, các phần tử còn lại có độ thuộc bằng 0.
  • Nén dữ liệu giao dịch mờ: Định nghĩa quan hệ khoảng cách giữa hai giao dịch mờ bằng số lượng mục khác nhau giữa chúng. Gộp các giao dịch có khoảng cách không vượt quá ngưỡng $d$ (khởi tạo $d = 1$) vào các khối $ML_k$, đồng thời tích lũy độ thuộc của các mục và cập nhật Bảng định lượng ($TL_k$).
  • Thuật toán khai phá luật mờ cải tiến: Kết hợp Bảng định lượng và cấu trúc dữ liệu nén để cắt tỉa không gian tìm kiếm ứng viên $C_r$ mà không cần quét toàn bộ cơ sở dữ liệu gốc, áp dụng nguyên lý đóng hướng xuống (downward closure).
  • Môi trường thực nghiệm: Các thuật toán được cài đặt bằng ngôn ngữ lập trình C#, chạy trên máy tính cấu hình phần cứng CPU Intel Core i5, bộ nhớ trong RAM 8GB.

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

Chương 1. Một số kiến thức cơ sở

Chương 1 hệ thống hóa toàn bộ nền tảng toán học và kỹ thuật cho các đề xuất của luận án:

  • Trình bày định nghĩa hình thức về tập mờ, các dạng hàm thuộc hình học phổ biến (hàm tam giác xác định bởi bộ ba tham số $a, b, c$; hàm hình thang xác định bởi bộ bốn $a, b, c, d$), khái niệm biến ngôn ngữ và phân hoạch mờ. Đưa ra 9 điều kiện chặt chẽ của một phân hoạch mờ, phân định rõ phân hoạch mờ mạnh ($\sum_{k=1}^m \mu_{A_k}(x) = 1$) và phân hoạch mờ đều. Phân biệt cấu trúc phân hoạch mờ đơn thể hạt và đa thể hạt.
  • Trình bày lý thuyết Đại số gia tử tuyến tính và tuyến tính đầy đủ, các tính chất bảo toàn trật tự của tập hạng từ $H(u)$, định lý so sánh hai hạng từ dựa trên biểu diễn chính tắc. Trình bày chi tiết công thức hàm dấu, độ đo tính mờ của gia tử $\mu(h)$, độ đo tính mờ của hạng từ $fm(x)$, hàm định lượng ngữ nghĩa $v(x)$ và cấu trúc khoảng tính mờ $\Im_{fm}(x)$. Luận án minh họa quá trình tính toán trên biến ngôn ngữ TRUTH và biến TUỔI với miền xác định $[0, 80]$, $fm(young) = 35/80 = 0.5625$, $\mu(L) = 0.4$, từ đó suy ra giá trị số thực của các nhãn ngôn ngữ như young, old, V young, L young, L old, V old.
  • Trình bày tổng quan về giải thuật di truyền (GA) và sơ đồ khối 5 bước cơ bản, cơ chế lai ghép, đột biến, chọn lọc; chi tiết hóa mô hình giải thuật CHC.
  • Định nghĩa bài toán khai phá luật kết hợp cổ điển, tập mục phổ biến, tập mục đóng (FCI), tập mục phổ biến lớn nhất (MFI), các tính chất cơ bản của độ hỗ trợ; chuyển tiếp sang bài toán khai phá luật kết hợp mờ, công thức tính $fs(\langle Z, C \rangle)$ và thuật toán khai phá luật mờ nền tảng theo lược đồ Apriori gồm 2 pha (pha 1 tìm tập phổ biến mờ $F_k$, pha 2 sinh luật thỏa mãn ngưỡng $fminconf$).

Chương 2. Khai phá luật kết hợp mờ theo hướng tiếp cận sử dụng đại số gia tử

Chương này tập trung vào hai đóng góp kỹ thuật cốt lõi: quy trình mờ hóa theo ĐSGT và thuật toán nén cơ sở dữ liệu giao dịch mờ.

  1. Phương pháp mờ hóa và xây dựng Bảng định lượng:

    • Mỗi thuộc tính định lượng được gán một cấu trúc ĐSGT. Thay vì phân chia tùy tiện, các điểm chia trên đoạn $[0, 1]$ được xác định trực tiếp từ hàm định lượng ngữ nghĩa $v(s_j)$ và khoảng tính mờ. Luận án lấy ví dụ minh họa với cấu trúc gồm 4 nhãn: Very Low ($A_1, B_1$), Least Low ($A_2, B_2$), Least Height ($A_3, B_3$), Very Height ($A_4, B_4$). Mỗi giá trị thuộc tính chỉ kích hoạt tối đa hai hàm thuộc liền kề, tổng độ thuộc bảo đảm bằng 1.
    • Định nghĩa quan hệ giao dịch và khoảng cách giao dịch mờ: Khoảng cách giữa hai giao dịch mờ là số lượng mục khác nhau giữa chúng. Ví dụ tính toán cụ thể trên 3 giao dịch $T_1, T_2, T_3$ cho thấy khoảng cách giữa $T_1$ và $T_2$ là $D_{T_1 - T_2} = 2$, giữa $T_2$ và $T_3$ là $D_{T_2 - T_3} = 4$.
    • Bảng định lượng ($TL$) được tổ chức theo tiền tố mục sắp xếp thứ tự từ điển, lưu trữ tổng giá trị hỗ trợ lũy tích theo độ dài giao dịch $L_1, \dots, L_n$, cho phép loại trừ nhanh các tập ứng viên không thỏa mãn độ hỗ trợ tối thiểu ($minsup$).

  2. Thuật toán nén giao dịch (Thuật toán 1) và khai phá luật mờ (Thuật toán 2):

    • Thuật toán 1 phân loại các giao dịch theo độ dài vào các khối $L_k$ và khối nhóm giao dịch $ML_k$. Khi duyệt từng giao dịch $T_i$, thuật toán tính khoảng cách với các nhóm hiện có trong $ML_{n-1}, ML_n, ML_{n+1}$. Nếu khoảng cách $\le d$ ($d = 1$), giao dịch được gộp vào nhóm và cộng dồn độ thuộc của các mục; nếu không, tiếp tục kiểm tra với các giao dịch đơn lẻ trong $L_{n-1}, L_n, L_{n+1}$ để tạo nhóm mới.
    • Thuật toán 2 áp dụng quy trình kiểu Apriori trên cơ sở dữ liệu nén, sử dụng Bảng định lượng tại mức $TL_r$ để cắt tỉa các ứng viên trước khi quét dữ liệu nén, giúp giảm số lần truy xuất bộ nhớ.

  3. Kết quả thử nghiệm đối chứng trên cơ sở dữ liệu FAM95:

    • Luận án tiến hành thử nghiệm so sánh 3 phương pháp trên tập dữ liệu FAM95 (63.565 bản ghi) với ngưỡng độ tin cậy cố định $minconf = 80%$, thay đổi ngưỡng độ hỗ trợ $minsup$ từ 20% đến 70%.
Độ hỗ trợ $minsup$ (%) CSDL không nén CSDL nén CSDL nén và Bảng định lượng
20 238 255 255
30 98 94 94
40 34 34 34
50 18 18 18
60 6 6 2
70 2 2 2

Số liệu thực nghiệm cho thấy tại các ngưỡng $minsup$ từ 40% đến 70%, số lượng luật kết hợp thu được giữa cơ sở dữ liệu gốc và cơ sở dữ liệu nén là tương đương nhau. Tại các ngưỡng thấp (20%, 30%), có sự chênh lệch nhỏ do cơ chế gộp giao dịch làm biến thiên cục bộ tần suất của một số mục biên. Đổi lại, việc sử dụng Bảng định lượng kết hợp nén giúp giảm rõ rệt thời gian thực thi của thuật toán so với việc xử lý trực tiếp trên tập dữ liệu đầy đủ.

Chương 3. Phân hoạch mờ cho thuộc tính dựa trên biểu diễn thể hạt của ĐSGT

Chương 3 giải quyết bài toán tự động xác định các hàm thuộc tối ưu từ dữ liệu số:

  • Biểu diễn thể hạt bằng ĐSGT: Phân tích các hạn chế của phương pháp rời rạc hóa cứng và phân hoạch mờ thông thường. Đề xuất phương pháp phân hoạch mờ dựa trên biểu diễn đơn thể hạt (single-granularity) và đa thể hạt (multi-granularity). Dưới cấu trúc ĐSGT, các khoảng tính mờ và giá trị SQM tự nhiên phân chia miền giá trị thuộc tính thành các hàm thuộc tam giác có tính chất ràng buộc lẫn nhau, bảo đảm là phân hoạch mờ mạnh (tổng độ thuộc bằng 1 tại mọi điểm), khắc phục tình trạng hàm thuộc bị méo mó.
  • Tối ưu hóa tham số mờ bằng giải thuật di truyền CHC:
    • Mã hóa nhiễm sắc thể biểu diễn các tham số mờ của ĐSGT (gồm độ đo tính mờ của phần tử sinh $fm(c^-)$ và độ đo tính mờ của các gia tử $\mu(h)$).
    • Xây dựng hàm mục tiêu kết hợp các độ đo đánh giá chất lượng phân hoạch mờ: độ phù hợp (Suitability - Suit), độ bao phủ (Coverage), độ chồng lấn (Overlap), số lượng tập 1-mục phổ biến (1-ItemSet) và độ thú vị trung bình (Average Interest) của các luật sinh ra.
    • Áp dụng lược đồ tìm kiếm phân hoạch tối ưu và khai phá luật kết hợp thông qua mô hình CHC.
  • Kết quả thực nghiệm chuyên sâu:
    • Tối ưu hóa tham số cho 10 thuộc tính với cả hai cấu trúc đơn thể hạt và đa thể hạt.
    • So sánh đối chứng với phương pháp của Herrera và cộng sự sử dụng lý thuyết tập mờ truyền thống. Kết quả cho thấy phương pháp dựa trên ĐSGT loại bỏ được các tập hàm thuộc phân bố lệch, giảm thiểu độ chồng lấn dư thừa giữa các tập mờ lân cận.
    • Đánh giá trên nhiều tập dữ liệu (Pollution, Stulong, Basketball, Quake, Stock): Phân tích quan hệ giữa số lượng tập 1-ItemSet, độ thú vị trung bình và các ngưỡng $minsup$. Biểu diễn đa thể hạt cho phép phát hiện các luật kết hợp ở nhiều mức chi tiết ngữ nghĩa khác nhau (từ mức khái quát đến mức đặc tả), phản ánh toàn diện các quy luật tiềm ẩn trong dữ liệu.

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. Thiết lập phương pháp luận biểu diễn tri thức mờ bằng Đại số gia tử: Luận án đề xuất một phương pháp tiếp cận có căn cứ toán học vững chắc để mờ hóa dữ liệu số và xây dựng hệ hàm thuộc. Khác với cách tiếp cận tập mờ trực giác, phương pháp này tận dụng tính trật tự ngữ nghĩa tự nhiên của ĐSGT, bảo đảm các hàm thuộc được sinh ra có sự liên kết cấu trúc chặt chẽ, tạo thành các phân hoạch mờ mạnh với tổng độ thuộc tại mọi điểm luôn bằng 1.
  2. Mô hình hóa phân hoạch mờ đa thể hạt: Luận án phát triển khung phân hoạch miền thuộc tính định lượng dựa trên biểu diễn đơn thể hạt và đa thể hạt của ĐSGT, cho phép biểu diễn các khái niệm ngôn ngữ theo phân tầng ngữ nghĩa từ khái quát đến chi tiết.
  3. Mô hình kết hợp ĐSGT và giải thuật di truyền CHC: Đề xuất giải pháp mã hóa các tham số mờ của ĐSGT ($fm(c^-), \mu(h)$) thành nhiễm sắc thể trong giải thuật di truyền CHC để tự động tìm kiếm cấu trúc phân hoạch tối ưu từ dữ liệu, khắc phục các khiếm khuyết về độ bao phủ và độ chồng lấn của phương pháp tối ưu tập mờ truyền thống.

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

  1. Thuật toán nén dữ liệu giao dịch mờ hiệu quả: Mở rộng thành công nguyên lý nén cơ sở dữ liệu từ dạng nhị phân sang cơ sở dữ liệu giao dịch mờ thông qua việc định nghĩa quan hệ khoảng cách mờ. Kết hợp với Bảng định lượng ($TL$), thuật toán giúp giảm thiểu kích thước không gian lưu trữ và cắt tỉa đáng kể số lượng tập ứng viên, từ đó rút ngắn thời gian quét dữ liệu khi khai phá tập phổ biến.
  2. Trích xuất tập luật ngôn ngữ có ý nghĩa: Thực nghiệm trên các tập dữ liệu thực tế (FAM95, STULONG, Pollution, Basketball, Quake, Stock) chứng minh hệ thống trích xuất được các luật kết hợp dạng ngôn ngữ tự nhiên, mạch lạc, dễ hiểu với người dùng và có độ thú vị cao, phục vụ thiết thực cho các hệ thống hỗ trợ ra quyết định và lập luận mờ.

Kiến nghị và giải pháp đề xuất từ tác giả

  • Ứng dụng cấu trúc ĐSGT thay thế các hàm thuộc mờ định tính thủ công trong các bài toán tiền xử lý dữ liệu cho khai phá tri thức (phân lớp, phân cụm, hồi quy mờ).
  • Tích hợp kỹ thuật nén cơ sở dữ liệu giao dịch mờ và bảng định lượng vào các hệ quản trị dữ liệu quy mô lớn nhằm tối ưu hóa chi phí tính toán khi khai thác luật định kỳ.

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

Hạn chế được ghi nhận từ văn bản

  • Độ biến động số lượng luật ở ngưỡng hỗ trợ thấp: Khi nén dữ liệu mờ với ngưỡng $minsup$ thấp (20%, 30%), số lượng luật khai phá được có sự chênh lệch nhất định so với việc khai phá trên dữ liệu gốc do quá trình gộp các giao dịch có khoảng cách gần nhau gây ra sai số tích lũy nhỏ về độ hỗ trợ của các mục biên.
  • Phạm vi dạng hàm thuộc: Luận án tập trung chủ yếu vào các hàm thuộc mờ dạng hình tam giác được sinh ra từ các khoảng tính mờ và giá trị SQM, chưa khảo sát sâu trên các dạng hình học phức tạp khác (như hình chuông Gauss hay hình thang suy biến).
  • Hạ tầng tính toán: Các thuật toán hiện mới được thử nghiệm tuần tự trên cấu hình máy tính đơn lẻ (Intel Core i5, RAM 8GB), chưa triển khai thực tế trên môi trường xử lý phân tán hoặc tính toán song song quy mô lớn.

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

  • Nghiên cứu cơ chế điều chỉnh ngưỡng khoảng cách $d$ động trong thuật toán nén để kiểm soát chặt chẽ hơn sai số độ hỗ trợ ở các mức $minsup$ rất thấp.
  • Mở rộng ứng dụng của hệ phân hoạch mờ dựa trên ĐSGT tối ưu sang các bài toán khai phá tri thức khác như phân lớp mờ, dự báo chuỗi thời gian và xây dựng cơ sở tri thức cho các hệ suy diễn mờ phức hợp.
  • Phát triển các phiên bản thuật toán khai phá luật mờ ĐSGT chạy trên môi trường tính toán song song và phân tán để xử lý các kho dữ liệu cực lớn.

Giá trị tham khảo

Đối tượng thụ hưởng

  • Nghiên cứu sinh và học viên cao học chuyên ngành Toán tin, Khoa học máy tính và Hệ thống thông tin: Tài liệu tham khảo toàn diện về phương pháp toán học ứng dụng Đại số gia tử vào bài toán xử lý thông tin mờ; cung cấp kỹ thuật kết hợp giữa logic mờ, giải thuật tiến hóa (GA) và khai phá dữ liệu.
  • Giảng viên và nhà nghiên cứu trong lĩnh vực Trí tuệ nhân tạo và Khai phá dữ liệu: Cung cấp khung lý thuyết chặt chẽ về phân hoạch mờ mạnh, biểu diễn dữ liệu đa thể hạt và cách thức giải quyết bài toán "điểm biên gãy" của các thuộc tính số thực.
  • Kỹ sư phát triển hệ thống và chuyên viên phân tích dữ liệu quản lý, kinh tế - xã hội: Cung cấp giải pháp kỹ thuật nén dữ liệu giao dịch và các thuật toán sinh luật kết hợp dạng ngôn ngữ tự nhiên, giúp xây dựng các hệ thống báo cáo tóm tắt ngôn ngữ (linguistic summaries) phục vụ công tác quản lý và hỗ trợ ra quyết định.

Các phần nội dung đáng tham khảo

  • Mục 1.2 & 1.3: Hệ thống hóa chi tiết các định nghĩa, định lý, công thức tính độ đo tính mờ, hàm định lượng ngữ nghĩa và khoảng tính mờ của Đại số gia tử kèm ví dụ tính số học cụ thể.
  • Mục 2.2, 2.3 & 2.4: Chi tiết mã giả của Thuật toán nén giao dịch mờ (Thuật toán 1), cấu trúc tổ chức Bảng định lượng, và Thuật toán khai phá dữ liệu mờ theo hướng tiếp cận ĐSGT (Thuật toán 2).
  • Mục 3.2 & 3.3: Khung thiết kế phân hoạch mờ đơn thể hạt, đa thể hạt và quy trình mã hóa tham số ĐSGT vào giải thuật di truyền CHC để tối ưu hóa hệ hàm thuộc.

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

1. Tại sao luận án sử dụng lý thuyết Đại số gia tử để thay thế cho lý thuyết tập mờ truyền thống trong bài toán phân hoạch thuộc tính định lượng?

Trong lý thuyết tập mờ truyền thống, việc xác định các tập mờ và hàm thuộc thường dựa vào trực giác hoặc ý kiến chủ quan của chuyên gia, không có cơ chế ràng buộc ngữ nghĩa nội tại giữa các nhãn từ, dẫn đến nguy cơ các hàm thuộc bị chồng lấn không hợp lý hoặc không phản ánh đúng phân bố dữ liệu. Đại số gia tử (ĐSGT) dựa trên cấu trúc toán học của quan hệ thứ tự tự nhiên của các từ ngôn ngữ. Bằng cách sử dụng độ đo tính mờ $fm(x)$ và hàm định lượng ngữ nghĩa $v(x)$, ĐSGT cho phép phân hoạch miền giá trị thành các khoảng tính mờ có ràng buộc ngữ nghĩa chặt chẽ. Hệ hàm thuộc tam giác xây dựng từ ĐSGT tự động bảo đảm tính chất của một phân hoạch mờ mạnh (tổng độ thuộc của bất kỳ điểm nào trên miền xác định đều bằng 1), giúp quá trình khai phá luật trở nên khách quan và ngữ nghĩa của các luật dễ chấp nhận hơn.

2. Thuật toán nén cơ sở dữ liệu giao dịch mờ trong Chương 2 hoạt động theo nguyên lý nào và có điểm gì khác so với thuật toán M2TQT?

Thuật toán M2TQT của Jia-Yu Dai và cộng sự (2008) chỉ áp dụng được trên cơ sở dữ liệu nhị phân ($0$ và $1$). Luận án đã mở rộng nguyên lý này sang cơ sở dữ liệu giao dịch mờ bằng cách:

  • Chuẩn hóa các thuộc tính về $[0, 1]$ và mờ hóa giá trị theo ĐSGT (mỗi giá trị chỉ ánh xạ vào tối đa hai nhãn mờ lân cận).
  • Định nghĩa khoảng cách giữa hai giao dịch mờ là số lượng mục khác nhau giữa chúng.
  • Khởi tạo khoảng cách quan hệ $d = 1$, tiến hành gộp các giao dịch có khoảng cách $\le d$ vào các khối nhóm giao dịch $ML_k$, đồng thời cộng dồn giá trị độ thuộc của các mục tương ứng và ghi nhận vào Bảng định lượng ($TL$). Quá trình này tạo ra cơ sở dữ liệu nén có kích thước nhỏ hơn hẳn cơ sở dữ liệu gốc, giúp thuật toán Apriori mờ cắt tỉa ứng viên sớm thông qua Bảng định lượng mà không cần duyệt toàn bộ dữ liệu.

3. Cấu trúc Bảng định lượng trong luận án được tổ chức như thế nào và có vai trò gì trong việc tăng tốc độ thuật toán?

Bảng định lượng được xây dựng đồng thời trong quá trình nén dữ liệu giao dịch. Các mục trong từng giao dịch được sắp xếp theo thứ tự từ điển; bảng ghi nhận chiều dài giao dịch $n$ và lưu trữ giá trị tích lũy độ thuộc của các mục theo từng cấp độ dài $L_1, L_2, \dots, L_n$. Nhờ có Bảng định lượng, khi sinh tập ứng viên kích thước $r$ ($C_r$), thuật toán có thể đối soát trực tiếp giá trị hỗ trợ lưu tại mức $TL_r$ để loại bỏ ngay các tập mục có độ hỗ trợ không đạt ngưỡng $minsup$ mà không cần thực hiện thao tác quét kiểm tra trên cơ sở dữ liệu nén, qua đó giảm đáng kể số lần truy cập dữ liệu và thời gian xử lý.

4. Giải thuật di truyền CHC được ứng dụng như thế nào trong việc tìm kiếm phân hoạch mờ tối ưu ở Chương 3?

Thay vì dùng GA truyền thống để tối ưu trực tiếp tọa độ các đỉnh của từng hàm thuộc riêng lẻ (dễ dẫn đến hàm thuộc biến dạng, phân bố lệch), luận án sử dụng GA mô hình CHC để tối ưu hóa bộ tham số mờ của cấu trúc ĐSGT cho từng thuộc tính (gồm độ đo tính mờ của phần tử sinh $fm(c^-)$ và độ đo tính mờ của các gia tử $\mu(h)$). Mô hình CHC sử dụng cơ chế chọn lọc dựa trên quần thể (chọn $N$ cá thể tốt nhất từ cả bố mẹ và con cái), áp dụng khoảng cách Hamming để ngăn ngừa lai tạo cận huyết và sử dụng kỹ thuật khởi tạo lại quần thể để duy trì tính đa dạng thay cho đột biến ngẫu nhiên. Hàm mục tiêu đánh giá cá thể kết hợp các tiêu chí: độ phù hợp (Suit), độ phủ (Coverage), độ chồng lấn (Overlap), số lượng tập 1-ItemSet và độ thú vị trung bình của luật.

5. Kết quả thử nghiệm trên tập dữ liệu FAM95 trong Bảng 2.4 cho thấy điều gì về tính chính xác và hiệu quả của phương pháp đề xuất?

Bảng 2.4 thống kê số lượng luật kết hợp thu được ở độ tin cậy 80% trên cơ sở dữ liệu FAM95 (63.565 bản ghi). Kết quả chỉ ra rằng ở các mức độ hỗ trợ trung bình và cao ($minsup$ từ 40% đến 70%), số lượng luật kết hợp trích xuất được từ cơ sở dữ liệu không nén, cơ sở dữ liệu nén, và cơ sở dữ liệu nén kết hợp Bảng định lượng là hoàn toàn trùng khớp (lần lượt là 34 luật ở 40%, 18 luật ở 50%, và 2 luật ở 70%). Ở các ngưỡng hỗ trợ thấp (20% và 30%), có sự sai khác nhẹ (ở 20% là 238 luật so với 255 luật; ở 30% là 98 luật so với 94 luật) do tác động gộp biên của khoảng cách giao dịch. Điều này chứng minh thuật toán nén bảo toàn tính đầy đủ của các luật quan trọng trong khi giảm thiểu chi phí quét dữ liệu.

Kết luận

Luận án của tác giả Nguyễn Tuấn Anh đã giải quyết thỏa đáng bài toán khai phá luật kết hợp mờ trên cơ sở dữ liệu định lượng bằng việc tích hợp lý thuyết Đại số gia tử với giải thuật di truyền CHC và kỹ thuật nén dữ liệu giao dịch mờ. Nghiên cứu đã chứng minh tính ưu việt của ĐSGT trong việc tạo lập các phân hoạch mờ mạnh có ngữ nghĩa chặt chẽ, đồng thời giải pháp nén dữ liệu kết hợp Bảng định lượng giúp giảm rõ rệt thời gian khai phá tập phổ biến. Các kết quả thực nghiệm trên các bộ dữ liệu FAM95, STULONG và các tập dữ liệu chuẩn đã kiểm chứng tính chính xác, tính khả thi và giá trị ứng dụng thực tiễn của các thuật toán đề xuất trong việc phát hiện tri thức dạng ngôn ngữ phục vụ hỗ trợ ra quyết định.