Tổng quan luận án
Luận án tiến sĩ chuyên ngành Khoa học máy tính / Công nghệ thông tin của tác giả Nguyễn Tuấn Anh (thực hiện 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, dưới sự hướng dẫn của PGS. Nguyễn Cát Hồ và TS.) tập trung giải quyết bài toán khai phá luật kết hợp mờ trên cơ sở dữ liệu chứa các thuộc tính định lượng thông qua lý thuyết Đại số gia tử (ĐSGT).
Tính cấp thiết và khoảng trống nghiên cứu
Trong khai phá dữ liệu và phát hiện tri thức, khai thác luật kết hợp từ các kho dữ liệu quy mô lớn là hướng tiếp cận cơ bản nhằm tìm kiếm các mối quan hệ tiềm ẩn phục vụ quản lý và phân tích nghiệp vụ. Khởi đầu từ bài toán luật kết hợp cổ điển của R. Agrawal (1993, 1994) vốn chỉ thao tác trên dữ liệu nhị phân (0 và 1), các nghiên cứu mở rộng sang dữ liệu số thực thường sử dụng phương pháp rời rạc hóa cứng. Kỹ thuật này phân chia miền giá trị định lượng thành các khoảng cách rời rạc, dẫn đến hiện tượng "điểm biên gãy" (sharp boundary problem). Để khắc phục, luật kết hợp mờ được đề xuất nhằm làm trơn biên phân chia bằng các hàm thuộc (Membership Functions - MF).
Tuy nhiên, các phương pháp khai phá luật kết hợp mờ truyền thống bộc lộ hai khoảng trống nghiên cứu chính:
- Hạn chế về tính chủ quan và cấu trúc của hàm thuộc: Hầu hết các phương pháp mờ hóa kinh điển đòi hỏi chuyên gia phải định nghĩa trước các tập mờ và hàm thuộc, hoặc nếu dùng giải thuật di truyền (GA) để tối ưu hóa thì các hàm thuộc ban đầu vẫn thiếu cơ sở ngữ nghĩa nội tại, dẫn đến độ chồng lấn cao và ngữ nghĩa của luật chưa tự nhiên.
- Hạn chế về hiệu năng tính toán: Các thuật toán khai phá luật kết hợp mờ có độ phức tạp hàm mũ do phải quét cơ sở dữ liệu (CSDL) nhiều lầ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 của Jia-Yu Dai, 2008) chỉ áp dụng cho dữ liệu nhị phân mà chưa xử lý được CSDL giao dịch mờ.
Mục tiêu và nhiệm vụ nghiên cứu
Văn bản luận án xác định các mục tiêu và nhiệm vụ cụ thể được đánh số như sau:
- Mục tiêu 1: Tìm kiếm một phương pháp luận cho phép phát hiện tri thức dạng luật mờ (luật kết hợp mờ với thông tin ngôn ngữ) từ CSDL số nhằm phát hiện các quan hệ dữ liệu tiềm ẩn, sử dụng cấu trúc toán học của Đại số gia tử thay thế cho lý thuyết tập mờ truyền thống.
- Mục tiêu 2: Đề xuất giải pháp nén dữ liệu giao dịch mờ dựa trên quan hệ khoảng cách giao dịch và bảng định lượng nhằm giảm kích thước CSDL, từ đó giảm thời gian thực hiện khai phá luật kết hợp.
- Mục tiêu 3: Đề xuất phương pháp tìm kiếm tập hàm thuộc tối ưu cho các thuộc tính định lượng bằng cách kết hợp lý thuyết ĐSGT và giải thuật di truyền (GA) theo mô hình CHC, áp dụng trên cả hai dạng biểu diễn dữ liệu là đơn thể hạt (single granularity) và đa thể hạt (multi-granularity).
Đối tượng và phạm vi nghiên cứu
- Đối tượng nghiên cứu: Các mô hình toán học và thuật toán khai phá luật kết hợp mờ; cấu trúc Đại số gia tử tuyến tính và đầy đủ; giải thuật di truyền mô hình CHC; kỹ thuật nén cơ sở dữ liệu giao dịch.
- Phạm vi dữ liệu và không gian thực nghiệm: Luận án thực nghiệm trên các bộ dữ liệu chuẩn:
- CSDL FAM95: Số liệu điều tra dân số Hoa Kỳ năm 1995 gồm 63.565 bản ghi với 5 thuộc tính được lựa chọn (Age, Hours, IncFam, IncHead, Sex).
- CSDL STULONG: Dữ liệu y tế nghiên cứu xơ vữa động mạch gồm 1.417 bản ghi với 5 thuộc tính định lượng số nguyên (A1, A2, A3, A4, A5).
- Các CSDL kiểm chứng bổ sung ở Chương 3: Pollution, Basketball, Quake, Stock.
- Môi trường tính toán: Thuật toán được cài đặt bằng ngôn ngữ C# và chạy thực nghiệm trên máy tính cá nhân cấu hình vi xử lý Intel Core i5, bộ nhớ trong RAM 8GB.
Tổng quan tài liệu và vị trí của luận án
Luận án đã tổng quan có hệ thống các công trình nghiên cứu trong và ngoài nước liên quan trực tiếp đến bài toán:
Các hướng nghiên cứu nền tảng và khai phá luật kết hợp
- Khai phá luật kết hợp nhị phân: Khởi xướng bởi R. Agrawal và cộng sự (1993, 1994) [21] với giải thuật kinh điển Apriori trên dữ liệu giỏ hàng (market basket data), định nghĩa hai độ đo cơ bản là Support và Confidence, cùng các độ đo mở rộng như Lift, Leverage, Conviction.
- Khai phá dữ liệu có thuộc tính định lượng: Srikant và Agrawal (1996) [8] tiếp cận bằng kỹ thuật rời rạc hóa miền giá trị thành các khoảng số học cứng.
- Khai phá luật kết hợp mờ: Kuok, Fu, Wong (1998) [27], Ishibuchi và cộng sự [30], cùng các nghiên cứu [29, 31, 57] đề xuất chuyển đổi thuộc tính định lượng sang tập mờ. Hạn chế cốt lõi là các hàm thuộc phải do chuyên gia thiết lập từ trước.
Các công trình tìm kiếm hàm thuộc tối ưu bằng giải thuật di truyền
Để giảm tính chủ quan của con người khi xây dựng hàm thuộc, một loạt tác giả đã ứng dụng giải thuật di truyền (GA) để tìm kiếm tham số hàm thuộc từ dữ liệu:
- Tzung-Pei Hong và các cộng sự qua các giai đoạn (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].
Luận án chỉ ra rằng dù các phương pháp trên đã tự động hóa việc tìm hàm thuộc, nhưng do xuất phát từ lý thuyết tập mờ thuần túy không có sự ràng buộc ngữ nghĩa giữa các nhãn ngôn ngữ, kết quả thu được qua GA vẫn có độ chồng lấn cao và thiếu tính chặt chẽ.
Hướng nghiên cứu ứng dụng Đại số gia tử vào khai phá dữ liệu
Lý thuyết Đại số gia tử do Nguyễn Cát Hồ và Wechler đề xuất (1990, 1992) [19, 49], sau đó được phát triển định lượng ngữ nghĩa bởi Nguyễn Cát Hồ và các cộng sự (2006, 2007) [25]. ĐSGT mô hình hóa miền giá trị ngôn ngữ thành một cấu trúc đại số có thứ tự toán học rõ ràng. Một số công trình ban đầu ứng dụng ĐSGT vào luật kết hợp mờ gồm:
- Nguyễn Công Hào và cộng sự (2012) [2]: Ánh xạ mỗi giá trị thuộc tính vào một phần tử duy nhất trong ĐSGT qua hàm ngược, dẫn đến nguy cơ mất mát thông tin.
- Nguyễn Nam Tiến và cộng sự (2012) [3]: Cải tiến bằng cách lưu cặp giá trị độ thuộc đối với hai phần tử định lượng ngữ nghĩa gần nhất về hai phía.
Hướng nghiên cứu nén CSDL giao dịch
- Jia-Yu Dai và cộng sự (2008) [18] đề xuất thuật toán M2TQT nén dữ liệu giao dịch nhị phân bằng cách gộp các bản ghi gần nhau.
- Chien-Min Lin (2013) [5] và Chun-Wei Lin cùng cộng sự (2009) [34] đề xuất cấu trúc nén CSDL trên cây FP-Tree.
Vị trí và khoảng trống luận án lựa chọn giải quyết
Luận án định vị nghiên cứu tại điểm giao thoa giữa cấu trúc toán học của ĐSGT, giải thuật nén dữ liệu giao dịch và kỹ thuật tối ưu hóa tiến hóa:
- Kế thừa mô hình biểu diễn cặp giá trị của Nguyễn Nam Tiến [3] nhưng phát triển thuật toán nén CSDL giao dịch mờ toàn diện kết hợp cấu trúc Bảng định lượng, giải quyết bài toán tăng tốc độ khai phá trên CSDL số thực bất kỳ.
- Vượt qua hạn chế của phương pháp tối ưu tập mờ truyền thống của Herrera [53] và Hong [42] bằng cách dùng ĐSGT làm khung sinh hàm thuộc tam giác, kết hợp giải thuật di truyền CHC trên cả biểu diễn đơn thể hạt và đa thể hạt.
Cơ sở lý thuyết và phương pháp nghiên cứu
Khung lý thuyết và khái niệm cốt lõi
- Lý thuyết tập mờ (Zadeh, 1965):
- 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]$. Các dạng hàm thuộc thông dụng gồm tam giác và hình thang.
- Biến ngôn ngữ được định nghĩa hình thức là bộ 5 thành phần $(X, T(X), U, R, M)$, trong đó $X$ là tên biến, $T(X)$ là tập giá trị ngôn ngữ, $U$ là không gian tham chiếu, $R$ là quy tắc cú pháp và $M$ là quy tắc ngữ nghĩa gán nhãn ngôn ngữ với tập mờ.
- Phân hoạch mờ gồm $m$ tập mờ $A_1, \dots, A_m$ trên $U = [a, b]$. Phân hoạch mờ được gọi là phân hoạch mờ mạnh khi thỏa mãn điều kiện:
$$\sum_{k=1}^m \mu_{A_k}(x) = 1, \quad \forall x \in U$$
- Lý thuyết Đại số gia tử:
- Một ĐSGT tuyến tính là bộ $AX = (X, G, H, \le)$, với $G = {c^-, W, c^+}$ là tập phần tử sinh ($c^-$ là phần tử sinh âm, $c^+$ là phần tử sinh dương, $W$ là phần tử trung hòa), $H = H^- \cup H^+$ là tập các gia tử âm và dương.
- ĐSGT tuyến tính đầy đủ bổ sung hai gia tử giới hạn cận trên $\sigma$ và cận dưới $\phi$, ký hiệu $AX^* = (X, G, H, \sigma, \phi, \le)$.
- Các đại lượng định lượng ngữ nghĩa của ĐSGT:
- Độ đo tính mờ của gia tử: $\mu(h) = \frac{fm(hx)}{fm(x)}$ không phụ thuộc vào hạng từ $x$.
- Độ đo tính mờ của hạng từ $fm(x)$ thỏa mãn $fm(c^-) + fm(c^+) = 1$ và $\sum_{h \in H} fm(hu) = fm(u)$.
- Hàm định lượng ngữ nghĩa (SQM) $v(x) \in [0, 1]$ xác định ánh xạ giá trị số cho từng hạng từ ngôn ngữ.
- Khoảng tính mờ $\Im_{fm}(x)$ có độ dài đúng bằng $fm(x)$. Phân hoạch dựa trên ĐSGT luôn tự nhiên tạo thành phân hoạch mờ mạnh.
- Bài toán khai phá luật kết hợp mờ:
- Cho CSDL giao dịch $D$ và tập mục $I$. Mỗi thuộc tính $i_j$ được gán với tập mờ, tạo thành tập thuộc tính mờ $\langle Z, C \rangle$.
- Độ hỗ trợ mờ $fs(\langle Z, C \rangle)$ và độ tin cậy mờ $FC((X, A), (Y, B))$ của luật "Nếu $X$ là $A$ thì $Y$ là $B$" được tính trên cơ sở tích độ thuộc của các thuộc tính trong từng giao dịch.
- Giải thuật di truyền mô hình CHC (Eshelman):
- Sử dụng cơ chế chọn lọc tinh hoa xuyên thế hệ (chọn $N$ cá thể tốt nhất từ cả bố mẹ và con cái).
- Cơ chế phòng tránh giao phối cận huyết: chỉ cho phép lai chéo hai cá thể nếu khoảng cách Hamming vượt quá một ngưỡng quy định; không sử dụng đột biến ngẫu nhiên mà kích thích đa dạng quần thể bằng phép khởi tạo lại (cataclysmic restart).
Phương pháp nghiên cứu thực nghiệm
Luận án áp dụng phương pháp định lượng và thực nghiệm thuật toán trên máy tính:
- Xây dựng quy trình mờ hóa ĐSGT: Chuẩn hóa miền thuộc tính về đoạn $[0, 1]$. Xác định vị trí giá trị $d_i^x$ nằm giữa giá trị định lượng ngữ nghĩa của hai phần tử ĐSGT lân cận $s_j, s_{j+1}$, tính độ thuộc theo công thức khoảng cách:
$$\mu_{s_j}(d_i^x) = 1 - |v(s_j) - d_i^x|$$
Các phần tử khác nhận độ thuộc bằng 0.
- Thiết kế cấu trúc dữ liệu nén: Khởi tạo ngưỡng khoảng cách $d = 1$. Xây dựng Bảng định lượng ($TL$) ghi nhận tiền tố mục và độ hỗ trợ tương ứng theo chiều dài giao dịch $L_1, \dots, L_n$. Gom cụm các giao dịch gần nhau vào khối nhóm giao dịch $ML_k$ và khối giao dịch đơn $L_k$.
- Đo lường và đánh giá: So sánh số lượng luật, độ hỗ trợ, độ tin cậy và thời gian xử lý (giây) giữa ba phương án: CSDL không nén, CSDL nén không bảng định lượng, và CSDL nén có bảng định lượng.
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 các nền tảng toán học và thuật toán làm tiền đề cho các đề xuất mới của luận án:
- Lý thuyết tập mờ và biến ngôn ngữ: Trình bày định nghĩa biến ngôn ngữ hình thức 5 thành phần, phân tích dạng hàm thuộc tam giác và hình thang. Định nghĩa phân hoạch mờ, phân hoạch mờ mạnh và phân hoạch mờ đều. Trình bày khái niệm đơn thể hạt (chỉ một mức phân hoạch) và đa thể hạt (nhiều mức chi tiết từ khái quát đến cụ thể).
- Lý thuyết Đại số gia tử: Giới thiệu cấu trúc đại số $AX = (X, G, H, \le)$, các định lý so sánh hai hạng từ dựa trên biểu diễn chính tắc và hàm dấu. Thiết lập phương pháp định lượng ngữ nghĩa thông qua độ đo tính mờ gia tử $\mu(h)$, độ đo tính mờ hạng từ $fm(x)$, hàm định lượng ngữ nghĩa $v(x)$ và khoảng tính mờ $\Im_k(x)$ mức $k$. Luận án đưa ra ví dụ tính toán số học trên biến TUỔI với $G = {young, old}$, $H = {V, L}$, $fm(young) = 35/80 = 0,5625$, $\mu(L) = 0,4$, từ đó suy ra giá trị số của các hạng từ: $v(V\ young) = 8,33$, $v(L\ young) = 26,58$, $v(L\ old) = 46,86$, $v(V\ old) = 68,91$ trên thang đo tuổi $[0, 80]$.
- Bài toán khai phá luật kết hợp và giải thuật di truyền: Trình bày thuật toán Apriori mờ 2 pha (pha 1 tìm tập mờ phổ biến thỏa mãn $fminsup$, pha 2 sinh luật thỏa mãn $fminconf$), các tính chất downward-closure để cắt tỉa tập ứng viên, và nguyên lý hoạt động của giải thuật di truyền mô hình CHC.
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 2 đề xuất giải pháp kỹ thuật giải quyết đồng thời việc mờ hóa thuộc tính và nén CSDL giao dịch nhằm giảm thời gian khai phá:
- Mờ hóa CSDL dựa trên ĐSGT: Mỗi thuộc tính định lượng được gán một cấu trúc ĐSGT tương ứng. Dữ liệu sau khi chuẩn hóa về $[0, 1]$ được tính độ thuộc vào hai nhãn ngôn ngữ liền kề dựa trên khoảng cách tới giá trị định lượng ngữ nghĩa $v(s_j)$, loại bỏ sự cần thiết phải vẽ hàm thuộc thủ công.
- Quan hệ giao dịch và khoảng cách giao dịch: Định nghĩa khoảng cách giữa hai giao dịch là số lượng các mục (item) khác nhau giữa chúng. Nếu khoảng cách nhỏ hơn hoặc bằng ngưỡng $d$ (khởi tạo $d = 1$), hai giao dịch được gộp thành một nhóm giao dịch mới, tổng độ thuộc của từng mục được cộng dồn.
- Bảng định lượng (Quantitative Table - TL): Được xây dựng đồng thời trong quá trình đọc giao dịch. Bảng ghi nhận các tiền tố mục xuất hiện trong các giao dịch có độ dài từ $L_1$ đến $L_n$. Thông tin này cho phép kiểm tra nhanh và loại bỏ sớm các tập ứng viên không thể đạt độ hỗ trợ tối thiểu mà không cần duyệt lại CSDL nén.
- Hệ thống thuật toán:
- Thuật toán 1 (Nén CSDL giao dịch mờ): Duyệt từng giao dịch mờ, tính độ dài, cập nhật Bảng định lượng, tính khoảng cách với các nhóm giao dịch trong khối $ML_{n-1}, ML_n, ML_{n+1}$ hoặc khối giao dịch $L_{n-1}, L_n, L_{n+1}$ để tiến hành gộp và cập nhật lại cấu trúc khối.
- Thuật toán 2 (Khai phá luật kết hợp mờ từ CSDL nén): Khai thác trên CSDL đã nén và Bảng định lượng theo tư tưởng Apriori, sử dụng $TL_r$ để cắt tỉa không gian tìm kiếm trước khi tính toán độ hỗ trợ thực tế.
- Kết quả thực nghiệm trên CSDL FAM95:
Bảng 2.4 dưới đây thống kê số lượng luật kết hợp thu được giữa các phương pháp ở các ngưỡng độ hỗ trợ khác nhau (với độ tin cậy cố định 80%):
| Độ hỗ trợ (%) |
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 |
Chi tiết các luật kết hợp thu được ở độ hỗ trợ 60% và độ tin cậy 80% được thống kê trong Bảng 2.5:
| STT |
Luật kết hợp |
Độ hỗ trợ (%) |
Độ tin cậy (%) |
| I |
CSDL không nén |
|
|
| 1 |
{ VL_INCHEAD } $\Rightarrow$ { VL_INCFAM } |
92 |
97 |
| 2 |
{ VL_INCFAM } $\Rightarrow$ { VL_INCHEAD } |
92 |
98 |
| 3 |
{ LY_AGE } $\Rightarrow$ { VL_INCHEAD } |
69 |
98 |
| 4 |
{ LY_AGE } $\Rightarrow$ { VL_INCFAM } |
70 |
99 |
| 5 |
{ VL_INCHEAD, LY_AGE } $\Rightarrow$ { VL_INCFAM } |
69 |
99 |
| 6 |
{ VL_INCFAM, LY_AGE } $\Rightarrow$ { VL_INCHEAD } |
69 |
99 |
| II |
CSDL nén, không dùng Bảng định lượng |
|
|
| 1 |
{ VL_INCHEAD } $\Rightarrow$ { VL_INCFAM } |
91 |
98 |
| 2 |
{ VL_INCFAM } $\Rightarrow$ { VL_INCHEAD } |
91 |
99 |
| 3 |
{ LY_AGE } $\Rightarrow$ { VL_INCHEAD } |
69 |
99 |
| 4 |
{ LY_AGE } $\Rightarrow$ { VL_INCFAM } |
69 |
100 |
| 5 |
{ VL_INCHEAD, LY_AGE } $\Rightarrow$ { VL_INCFAM } |
69 |
100 |
| 6 |
{ VL_INCFAM, LY_AGE } $\Rightarrow$ { VL_INCHEAD } |
69 |
99 |
| III |
CSDL nén và Bảng định lượng |
|
|
| 1 |
{ VL_INCHEAD } $\Rightarrow$ { VL_INCFAM } |
91 |
98 |
| 2 |
{ VL_INCFAM } $\Rightarrow$ { VL_INCHEAD } |
91 |
99 |
| 3 |
{ LY_AGE } $\Rightarrow$ { VL_INCHEAD } |
69 |
99 |
| 4 |
{ LY_AGE } $\Rightarrow$ { VL_INCFAM } |
69 |
100 |
| 5 |
{ LY_AGE, VL_INCHEAD } $\Rightarrow$ { VL_INCFAM } |
69 |
100 |
| 6 |
{ LY_AGE, VL_INCFAM } $\Rightarrow$ { VL_INCHEAD } |
69 |
99 |
Ở ngưỡng độ hỗ trợ 70% và độ tin cậy 80% (Bảng 2.6), cả ba phương pháp đều thu được đúng 2 luật cốt lõi:
{ VL_INCHEAD } $\Rightarrow$ { VL_INCFAM } (Độ hỗ trợ 92%, Tin cậy 97% trên CSDL gốc; Độ hỗ trợ 91%, Tin cậy 98% trên CSDL nén).{ VL_INCFAM } $\Rightarrow$ { VL_INCHEAD } (Độ hỗ trợ 92%, Tin cậy 98% trên CSDL gốc; Độ hỗ trợ 91%, Tin cậy 99% trên CSDL nén).
Về thời gian thực thi (Hình 2.3 và Hình 2.4), phương pháp sử dụng CSDL nén có thời gian tính toán giảm vượt trội so với CSDL không nén ở mọi ngưỡng hỗ trợ (ở ngưỡng 10%, thời gian giảm từ trên 1400 giây xuống dưới 400 giây); việc tích hợp thêm Bảng định lượng tiếp tục rút ngắn thời gian xử lý xuống mức thấp hơn đáng kể.
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 tập trung giải quyết bài toán tự động sinh và tối ưu hóa hệ hàm thuộc mờ:
- Xây dựng phân hoạch mờ từ ĐSGT: Dựa vào giá trị định lượng ngữ nghĩa $v(x)$ làm đỉnh và khoảng tính mờ $\Im(x)$ làm đáy tam giác, các hàm thuộc tam giác được sinh tự động. Cấu trúc này đảm bảo tính chất phân hoạch mờ mạnh ($\sum \mu = 1$), khắc phục hiện tượng phân bố lệch hoặc chồng lấn không kiểm soát của phương pháp tập mờ truyền thống.
- Biểu diễn đơn thể hạt và đa thể hạt:
- Đơn thể hạt: Phân hoạch miền giá trị ở một mức độ chi tiết cố định.
- Đa thể hạt: Phân hoạch theo cấu trúc hình cây nhiều mức, cho phép các nhãn ngôn ngữ chuyển hóa linh hoạt từ khái quát đến chi tiết đặc tả.
- Tối ưu hóa tham số mờ bằng GA mô hình CHC:
- Nhiễm sắc thể mã hóa các tham số cơ sở của ĐSGT gồm độ đo tính mờ phần tử sinh $fm(c^-)$ và độ đo tính mờ của các gia tử $\mu(h)$.
- Thiết kế hàm mục tiêu kết hợp các tiêu chí đánh giá heuristic: độ phù hợp của hàm thuộc (Suitability), độ bao phủ dữ liệu, số lượng tập phổ biến 1-ItemSet, và độ thú vị trung bình của luật.
- Thực nghiệm so sánh: Triển khai trên các CSDL STULONG, FAM95, Pollution, Basketball, Quake, Stock. Kết quả đối chiếu với phương pháp kinh điển của Herrera [53] (sử dụng GA trên tập mờ thông thường) cho thấy: hệ hàm thuộc sinh bởi ĐSGT phân bố cân đối, không xuất hiện các hàm thuộc bị triệt tiêu; mô hình đa thể hạt khai phá được tập luật phong phú hơn với độ thú vị trung bình cao hơn rõ rệt.
Kết quả và những đóng góp mới
Đóng góp mới về mặt lý luận
- Luận án xây dựng thành công phương pháp luận sử dụng lý thuyết Đại số gia tử để phân hoạch mờ miền xác định của các thuộc tính định lượng trong CSDL giao dịch. Phương pháp chứng minh rằng các phân hoạch mờ xây dựng từ giá trị định lượng ngữ nghĩa và khoảng tính mờ của ĐSGT tự động tạo thành phân hoạch mờ mạnh, giữ vững cấu trúc thứ tự tự nhiên của ngôn ngữ và giảm tính chủ quan của chuyên gia.
- Thiết lập mô hình biểu diễn đa thể hạt dựa trên ĐSGT, cung cấp cơ chế biểu diễn tri thức luật mờ ở nhiều mức độ hạt khác nhau (từ bao quát đến chi tiết cụ thể).
- Đề xuất quy trình tích hợp giải thuật di truyền mô hình CHC để tối ưu hóa bộ tham số mờ nội tại của ĐSGT ($fm$ và $\mu$), khắc phục hạn chế không gian tìm kiếm tự do, rời rạc của các phương pháp tối ưu hàm thuộc mờ truyền thống.
Đóng góp mới về mặt thực tiễn
- Đề xuất thuật toán nén CSDL giao dịch mờ dựa trên khoảng cách giao dịch và cấu trúc Bảng định lượng ($TL$). Thuật toán cho phép giảm đáng kể kích thước CSDL giao dịch đầu vào, tạo điều kiện tăng tốc độ xử lý của các giải thuật khai phá luật dạng Apriori.
- Xây dựng chương trình thử nghiệm hoàn chỉnh trên ngôn ngữ C#, kiểm chứng tính đúng đắn và hiệu quả trên các tập dữ liệu thực nghiệm quy mô lớn (FAM95 với hơn 63.000 bản ghi, STULONG, Pollution, Basketball, Quake, Stock).
Kiến nghị và giải pháp đề xuất
- Ứng dụng quy trình nén dữ liệu giao dịch mờ và biểu diễn ĐSGT vào các hệ thống quản trị dữ liệu quy mô lớn trong lĩnh vực kinh tế - xã hội, điều tra dân số và phân tích bệnh án y tế.
- Khuyến nghị áp dụng mô hình phân hoạch mờ đa thể hạt bằng ĐSGT làm tiền xử lý cho các bài toán phân lớp dữ liệu (classification), dự báo và hồi quy mờ.
Hạn chế và hướng nghiên cứu tiếp
Hạn chế của nghiên cứu
Theo phạm vi và dữ liệu thực tế được văn bản phản ánh:
- Thuật toán nén CSDL mờ sử dụng ngưỡng khoảng cách cố định khởi tạo ban đầu ($d = 1$), chưa có cơ chế tự động điều chỉnh ngưỡng $d$ linh hoạt theo phân bố cục bộ của dữ liệu.
- Việc gộp các giao dịch gần nhau dẫn đến độ hỗ trợ và độ tin cậy của một số luật có sự chênh lệch nhỏ so với khi quét trên CSDL gốc (sai số khoảng 1% như thể hiện tại Bảng 2.5 và Bảng 2.6).
- Dạng hình học của hàm thuộc xây dựng từ ĐSGT trong luận án mới chỉ tập trung vào dạng hàm tam giác.
- Môi trường thử nghiệm thực hiện trên cấu hình máy đơn luồng (CPU Intel Core i5, RAM 8GB), chưa triển khai trên môi trường tính toán song song hay phân tán.
Hướng nghiên cứu tiếp
- Nghiên cứu cơ chế tự thích nghi cho ngưỡng khoảng cách $d$ trong thuật toán nén giao dịch.
- Mở rộng thuật toán nén và khai phá luật kết hợp mờ ĐSGT trên các kiến trúc tính toán song song, điện toán đám mây hoặc nền tảng dữ liệu lớn.
- Phát triển các cấu trúc hàm thuộc phi tuyến khác dựa trên ĐSGT và ứng dụng mô hình đa thể hạt vào hệ thống lập luận xấp xỉ và suy diễn mờ.
Giá trị tham khảo
Đối tượng thụ hưởng
- Nghiên cứu sinh, học viên cao học và giảng viên ngành Khoa học máy tính, Công nghệ thông tin: Cung cấp tài liệu tham khảo có cấu trúc toán học chặt chẽ về việc kết hợp Đại số gia tử với các kỹ thuật khai phá dữ liệu tiên tiến.
- Các nhà nghiên cứu tính toán mềm (Soft Computing) và Trí tuệ nhân tạo: Tài liệu hữu ích cho hướng nghiên cứu biểu diễn tri thức ngôn ngữ, tối ưu hóa tiến hóa và phân hoạch dữ liệu thể hạt.
- Chuyên viên phân tích dữ liệu và kỹ sư hệ thống thông tin: Tham khảo giải pháp nén dữ liệu giao dịch và quy trình trích xuất luật ngôn ngữ dễ hiểu trên các kho dữ liệu định lượng thực tế.
Các phần nội dung có giá trị tham khảo nổi bật
- Mục 1.2 & 1.3 (Chương 1): Các định lý toán học, công thức tính toán cụ thể về hàm định lượng ngữ nghĩa và khoảng tính mờ của ĐSGT tuyến tính đầy đủ.
- Thuật toán 1 & Bảng định lượng (Chương 2): Thiết kế chi tiết về cấu trúc dữ liệu và quy trình nén giao dịch mờ cùng cơ chế cắt tỉa ứng viên sớm.
- Quy trình tối ưu hóa GA CHC (Chương 3): Phương pháp mã hóa nhiễm sắc thể tham số ĐSGT và hàm mục tiêu đánh giá chất lượng phân hoạch mờ.
Câu hỏi thường gặp
1. Cơ chế mờ hóa một giá trị định lượng theo tiếp cận ĐSGT trong luận án được thực hiện như thế nào?
Giá trị thuộc tính số trước hết đượ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, giá trị thực tế $d_i^x$ sẽ nằm giữa hai giá trị định lượng ngữ nghĩa của hai phần tử liền kề. Luận án tính độ thuộc của $d_i^x$ vào hai phần tử này theo công thức $\mu_{s_j}(d_i^x) = 1 - |v(s_j) - d_i^x|$, trong khi độ thuộc vào tất cả các phần tử còn lại trong ĐSGT được gán bằng 0. Mỗi giá trị số được biểu diễn bởi một cặp giá trị độ thuộc.
2. Nguyên lý nén cơ sở dữ liệu giao dịch mờ của Thuật toán 1 là gì?
Thuật toán dựa trên quan hệ khoảng cách giao dịch, định nghĩa bằng số lượng mục khác nhau giữa hai giao dịch mờ. Nếu khoảng cách giữa giao dịch mới và nhóm giao dịch sẵn có nhỏ hơn hoặc bằng ngưỡng quy định ($d = 1$), giao dịch đó sẽ được gộp vào nhóm và tổng độ thuộc của từng mục được cộng dồn. Dữ liệu nén được tổ chức thành các khối $ML_k$ (nhóm giao dịch) và $L_k$ (giao dịch đơn) theo độ dài $k$.
3. Bảng định lượng ($TL$) đóng vai trò gì trong việc tăng tốc độ thuật toán khai phá luật?
Bảng định lượng được xây dựng đồng thời trong quá trình duyệt nén dữ liệu, lưu trữ thông tin tiền tố mục và giá trị tích lũy độ hỗ trợ tương ứng theo các mức chiều dài giao dịch từ $L_1$ đến $L_n$. Khi sinh các tập mục ứng viên mức $r$ ($C_r$), thuật toán tra cứu giá trị $TL_r$ để loại bỏ ngay các ứng viên không đạt ngưỡng độ hỗ trợ tối thiểu ($min_sup$) mà không cần duyệt qua CSDL nén, giúp tiết kiệm đáng kể thời gian quét dữ liệu.
4. Tại sao giải thuật di truyền mô hình CHC lại được lựa chọn thay thế cho GA kinh điển?
Mô hình CHC sử dụng chiến lược chọn lọc tinh hoa bảo tồn thế hệ (lựa chọn $N$ cá thể tốt nhất từ cả quần thể cha mẹ và con cái), kết hợp cơ chế kiểm soát khoảng cách Hamming khi lai chép để ngăn ngừa hiện tượng giao phối cận huyết. Mô hình này không sử dụng phép đột biến thông thường mà dùng phép tái khởi tạo quần thể (cataclysmic restart) khi độ đa dạng suy giảm, giúp thuật toán tránh rơi vào cực trị địa phương và hội tụ ổn định hơn khi tối ưu các tham số $fm$ và $\mu$ của ĐSGT.
5. Kết quả thực nghiệm trên tập dữ liệu FAM95 thể hiện tính hiệu quả của phương pháp nén dữ liệu như thế nào?
Trên tập FAM95 (63.565 bản ghi), ở ngưỡng hỗ trợ từ 40% đến 70% (độ tin cậy 80%), số lượng luật khai phá được từ CSDL nén hoàn toàn trùng khớp với CSDL gốc không nén. Sự khác biệt về độ hỗ trợ và độ tin cậy của từng luật chỉ dao động trong khoảng 1%. Trong khi đó, thời gian xử lý của CSDL nén giảm rõ rệt; ví dụ ở ngưỡng hỗ trợ 10%, thời gian thực thi giảm từ hơn 1400 giây xuống dưới 400 giây, và tiếp tục giảm sâu hơn khi áp dụng kèm Bảng định lượng.
Kết luận
Luận án tiến sĩ của tác giả Nguyễn Tuấn Anh đã giải quyết bài toán khai phá luật kết hợp mờ trên CSDL định lượng bằng cách kết hợp lý thuyết Đại số gia tử, kỹ thuật nén dữ liệu giao dịch và giải thuật di truyền CHC. Các đóng góp chính bao gồm quy trình mờ hóa bảo toàn tính phân hoạch mờ mạnh của ĐSGT, thuật toán nén CSDL mờ tích hợp Bảng định lượng giúp giảm thời gian tính toán, và phương pháp tự động tối ưu hóa tham số mờ trên cả hai cấu trúc đơn thể hạt và đa thể hạt. Các kết quả thực nghiệm trên CSDL FAM95, STULONG và nhiều bộ dữ liệu benchmark đã chứng minh tính đúng đắn, độ tin cậy và giá trị ứng dụng thực tiễn của toàn bộ phương pháp luận được đề xuất.
