Tóm tắt Luận án Nghiên cứu phát triển phương pháp khai phá luật kết hợp mờ biểu thị bằng thông tin ngôn ngữ và ứng dụng

: Dữ liệu giao dịch thứ i, 1 ≤ 𝑖 ≤ 𝑁 𝑣𝑗 (𝑘) : Giá trị phần tử thứ k của Aj trong D (i) Hình 2.2: Tổng quan về thuật toán nén CSDL giao dịch 8 𝑓𝑗𝑘 (𝑖) : Giá trị độ thuộc của 𝑣j (k) với nhãn gia tử Rjk, 0 ≤ 𝑓𝑗𝑘 (𝑖) ≤ 1 𝑆𝑢𝑝(𝑅𝑗𝑘): Độ hỗ trợ của Rjk Sup: Giá trị hỗ trợ của mỗi tập mục phổ biến Conf: Độ tin cậy của mỗi tập mục phổ biến Min_sup: Độ hỗ trợ tối thiểu cho trước Min_conf: Độ tin tin cậy cho trước 𝐶𝑟: Tập các tập mục có khả năng với r thuộc tính (tập mục), 1 ≤ 𝑟 ≤ 𝑚 𝐿𝑟: Tập các tập mục phổ biến thỏa mãn với r nhãn gia tử (tập mục) 1 ≤ 𝑟 ≤ 𝑚. Thuật toán khai phá luật kết hợp dựa trên ĐSGT cho các giá trị định lượng được thực hiện như sau: Input: CSDL giao tác D; Các ĐSGT cho các thuộc tính mờ; Độ hỗ trợ 𝑀𝑖𝑛_𝑠𝑢𝑝 và độ tin cậy 𝑀𝑖𝑛_𝑐𝑜𝑛𝑓. Output: Luật kết hợp mờ Bước 1: Chuyển các giá trị định lượng 𝑣𝑗 (𝑘) của giao dịch 𝐴𝑗 trong 𝐷 (𝑖), với i từ 1 tới N. Với 𝑣𝑗 (𝑘) , nếu 𝑣𝑗 (𝑘) nằm ở ngoài 1 trong 2 đầu mút (2 nhãn gia tử cực đại và cực tiểu) thì 𝑣𝑗 (𝑘) chỉ có 1 nhãn gia tử ứng với đầu mút đó. Ngược lại 𝑣𝑗 (𝑘) được biểu diễn bởi 2 nhãn gia tử liên tiếp có đoạn giá trị nhỏ nhất trên trường giá trị của 𝑣𝑗 (𝑘) , mỗi nhãn ứng với 1 giá trị biểu diễn độ thuộc 𝑓𝑗𝑘 (𝑖) (j = 1, 2) của 𝑣𝑗 (𝑘) với nhãn gia tử đó. Độ thuộc này được tính là khoảng cách của 𝑣𝑗 (𝑘) tới giá trị biểu diễn cho nhãn gia tử tương ứng. Bước 2: Thực hiện thuật toán nén giao dịch (Thuật toán 1) với CSDL được mờ hóa ở Bước 1. Kết thúc bước này, chúng ta thu được CSDL giao dịch nén và bảng định lượng. Chúng ta sử dụng thuật toán giống như Apriori với CSDL nén để sinh ra các tập phổ biến. Bước 3: Dựa vào giá trị trong TL1 của bảng định lượng, giá trị trong TL1 là độ hỗ trợ của các 𝑅𝑗𝑘. Nếu 𝑆𝑢𝑝(𝑅𝑗𝑘) ≥ min_𝑠𝑢𝑝 thì đưa Rjk vào L1. Bước 4: Nếu L1 ≠ ∅, tiếp tục bước sau, nếu L1 = ∅ thì kết thúc thuật toán. Bước 5: Thuật toán xây dựng tập mục phổ biến mức r từ các tập mục phổ biến mức r - 1 bằng cách chọn 2 tập mục phổ biến mức r - 1 chỉ khác nhau duy nhất một mục, hợp 2 tập mục này ta được tập mục ứng viên 𝐶𝑟. Trước khi sử dụng CSDL nén để tính độ hỗ trợ của các tập mục trong 𝐶𝑟, dựa vào giá trị của TLr trong bảng định lượng chúng ta có thể loại bớt một số ứng cử viên mà không cần phải duyệt CSDL nén. Bước 6: Duyệt CSDL nén, tính độ hỗ trợ của mỗi tập mục trong 𝐶𝑟. Nếu tập mục nào có độ hỗ trợ thỏa mãn độ hỗ trợ tối thiểu thì đưa vào 𝐿𝑟. Bước 7: Thực hiện theo các bước con sau đây lặp lại cho các tập mục phổ biến mức lớn hơn được sinh ra tiếp theo dạng (r+1) tập mục phổ biến S với mục (𝑠1, 𝑠2, , 𝑠𝑡 , , 𝑠𝑟+1) trong 𝐶𝑟+1, 1 ≤ 𝑡 ≤ 𝑟 + 1. (a) Tính giá trị hỗ trợ sup(S) của S trong giao dịch (b) Nếu 𝑆𝑢𝑝(𝑆) ≥ 𝑀𝑖𝑛_𝑠𝑢𝑝, thì đưa S vào 𝐿𝑟+1 Bước 8: Nếu Lr+1 là rỗng, thì thực hiện bước tiếp theo, ngược lại, đặt 𝑟 = 𝑟 + 1, thực hiện lại bước 6 và 7. Bước 9: Đưa ra các luật kết hợp từ các tập mục phổ biến vừa thu được. 9 2.5. Kết quả thử nghiệm Kết quả thực nghiệm được thực hiện với hai thuật toán: thuật toán đề xuất và thuật toán Apriori mờ bằng ngôn ngữ lập trình C# và chạy thử nghiệm trên máy tính có cấu hình như sau: Intel(R) Core(TM) i5 CPU 1.7GHz, RAM 6GB. Trong chương này, luận án sử dụng hai CSDL để thử nghiệm: FAM95 và STULONG. 2.5.1. Thử nghiệm với CSDL FAM95 Trong Bảng 2.4 thống kê số lượng luật kết hợp thu được của ba phương pháp: phương pháp sử dụng: CSDL không nén, CSDL nén, và CSDL nén và Bảng định lượng. Với độ hỗ trợ 20%, 30% số lượng luật kết hợp của phương pháp luận án đề xuất có khác so với phương pháp sử dụng thuật toán Apriori, với độ hỗ trợ tử 40% đến 70% thì số lượng luật kết hợp thu được của ba phương pháp là giống nhau. Bảng 2.4: Số lượng luật kết hợp thu được với độ tin cậy 80% Độ hỗ trợ (%) Sử dụ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 6 70 2 2 2 Trong Bảng 2.5, Bảng 2.6 cho thấy số lượng luật kết hợp thu được của ba thử nghiệm (với CSDL không nén, CSDL nén không sử dụng bảng định lượng, CSDL nén sử dụng bảng định lượng) có số lượng giống nhau. Trong Bảng 2.5 so sánh tương ứng từng luật của ba phương pháp cho thấy độ hỗ trợ và độ tin cậy của mỗi luật có khác nhau nhưng không đáng kể. Bảng 2.5: Luật kết hợp thu được với độ hỗ trợ 60% và độ tin cậy 80% STT Luật kết hợp Đỗ hỗ trợ Độ tin cậy CSDL không nén 1 { VL_INCHEAD } ==> { VL_INCFAM } 92% 97% 2 { VL_INCFAM } ==> { VL_INCHEAD } 92% 98% 3 { LY_AGE } ==> { VL_INCHEAD } 69% 98% 4 { LY_AGE } ==> { VL_INCFAM } 70% 99% 5 { VL_INCHEAD, LY_AGE } ==> { VL_INCFAM } 69% 99% 6 { VL_INCFAM, LY_AGE } ==> { VL_INCHEAD } 69% 99% CSDL giao dịch nén, không sử dụng bảng định lượng 1 { VL_INCHEAD } ==> { VL_INCFAM } 91% 98% 2 { VL_INCFAM } ==> { VL_INCHEAD } 91% 99% 3 { LY_AGE } ==> { VL_INCHEAD } 69% 99% 4 { LY_AGE } ==> { VL_INCFAM } 69% 100% 5 { VL_INCHEAD, LY_AGE } ==> { VL_INCFAM } 69% 100% 6 { VL_INCFAM, LY_AGE } ==> { VL_INCHEAD } 69% 99% CSDL giao dịch nén, và sử dụng bảng định lượng 1 { VL_INCHEAD } ==> { VL_INCFAM } 91% 98% 2 { VL_INCFAM } ==> { VL_INCHEAD } 91% 99% 3 { LY_AGE } ==> { VL_INCHEAD } 69% 99% 4 { LY_AGE } ==> { VL_INCFAM } 69% 100% 5 { LY_AGE, VL_INCHEAD } ==> { VL_INCFAM } 69% 100% 6 { LY_AGE, VL_INCFAM } ==> { VL_INCHEAD } 69% 99% 10 Bảng 2.6: Luật kết hợp thu được với độ hỗ trợ 70% và độ tin cậy 80% STT Luật kết hợp Đỗ hỗ trợ Độ tin cậy CSDL không nén 1 { VL_INCHEAD } ==> { VL_INCFAM } 92% 97% 2 { VL_INCFAM } ==> { VL_INCHEAD } 92% 98% CSDL giao dịch nén, không sử dụng bảng định lượng 1 { VL_INCHEAD } ==> { VL_INCFAM } 91% 98% 2 { VL_INCFAM } ==> { VL_INCHEAD } 91% 99% CSDL giao dịch nén, và sử dụng bảng định lượng 1 { VL_INCHEAD } ==> { VL_INCFAM } 91% 98% 2 { VL_INCFAM } ==> { VL_INCHEAD } 91% 99% Hình 2.3: Thời gian thực hiện với CSDL nén Trong Hình 2.3 so sánh thời gian thực thuật toán Apriori mờ với CSDL không nén và thời gian thực hiện với CSDL nén nhưng không sử dụng bảng định lượng. Trong Hình 2.4 so sánh thời gian thực hiện thuật toán cùng với CSDL nén có sử dụng bảng định lượng và CSDL nén không sử dụng bảng định lượng. Thời gian dùng để nén CSDL trên là 135 giây, số giao dịch thu được sau khi nén là 2402 giao dịch. Kết quả thử nghiệm với độ tin cậy là 60%, luận án thử nghiệm với hai thuật toán: Luật kết hợp theo cách tiếp cận của ĐSGT [2] và thuật toán luận án đề xuất là nén CSDL mờ theo hướng tiếp cận ĐSGT. Kết quả thử nghiệm cho thấy phương pháp đề xuất nén CSDL cho kết quả nhanh hơn với phương pháp đề xuất trong [2] và giá trị của các tập phổ biến tìm được giống với khi chúng ta sử dụng CSDL không nén. 2.5.2. Thử nghiệm với CSDL STULONG Trong Bảng 2.7 thống kê số lượng luật kết hợp thu được của ba phương pháp: phương pháp sử dụng: CSDL không nén, CSDL nén, và CSDL nén và Bảng định lượng. Bảng 2.7: Số lượng luật kết hợp thu được với độ tin cậy 80% Độ hỗ trợ (%) CSDL không nén CSDL nén CSDL nén, và Bảng định lượng 5% 7822 8188 8185 10% 5076 5532 5527 20% 2149 2528 2528 30% 1096 1348 1318 40% 587 599 599 50% 248 287 287 60% 107 155 155 70% 75 75 75 80% 23 35 35 Nhận xét: số lượng luật kết hợp thu được của phương pháp luận án đề xuất sử dụng CSDL nén có sử dụng bảng định lương và không sử dụng bảng định lượng cơ bản là giống nhau. Bảng 2.8: So sánh thời gian thực hiện khai phá luật kết hợp với độ tin cậy 80% Độ hỗ trợ (%) CSDL không nén CSDL nén CSDL nén, và Bảng định lượng 5% 669 41.4 41.4 10% 580 26.4 26.3 20% 187 8.3 8.3 30% 72 3.6 3.5 40% 26 1.1 1.1 50% 8 0.4 0.4 11 60% 3 0.2 0.2 70% 1 0.1 0.1 Trong Bảng 2.9, Bảng 2.10 cho thấy số lượng luật kết hợp thu được của ba thử nghiệm (với CSDL không nén, CSDL nén không sử dụng bảng định lượng, CSDL nén sử dụng bảng định lượng) có số lượng luật kết hợp giống nhau. Trong Bảng 2.9, Bảng 2.10 so sánh tương ứng từng luật của ba phương pháp cho thấy độ hỗ trợ và độ tin cậy của mỗi luật có khác nhau nhưng không đáng kể. Bảng 2.9: Luật kết hợp thu được với độ hỗ trợ 85% và độ tin cậy 80% STT Luật kết hợp Đỗ hỗ trợ Độ tin cậy CSDL không nén 1 { LL_A5 } ==> { LH_A2 } 86 % 97 % 2 { LH_A2 } ==> { LL_A5 } 86 % 93 % 3 { LL_A5 } ==> { VH_A1 } 88 % 99 % 4 { VH_A1 } ==> { LL_A5 } 88 % 91 % 5 { LH_A2 } ==> { VH_A1 } 92 % 99 % 6 { VH_A1 } ==> { LH_A2 } 92 % 95 % 7 { LL_A5, VH_A1 } ==> { LH_A2 } 85 % 97 % 8 { LH_A2, VH_A1 } ==> { LL_A5 } 85 % 93 % 9 { LH_A2, LL_A5 } ==> { VH_A1 } 85 % 100 % CSDL giao dịch nén, không Bảng định lượng 1 { LL_A5 } ==> { LH_A2 } 88 % 99 % 2 { LH_A2 } ==> { LL_A5 } 88 % 95 % 3 { LL_A5 } ==> { VH_A1 } 88 % 100 % 4 { VH_A1 } ==> { LL_A5 } 88 % 91 % 5 { LH_A2 } ==> { VH_A1 } 92 % 100 % 6 { VH_A1 } ==> { LH_A2 } 92 % 95 % 7 { LL_A5, VH_A1 } ==> { LH_A2 } 87 % 99 % 8 { LH_A2, VH_A1 } ==> { LL_A5 } 87 % 95 % 9 { LH_A2, LL_A5 } ==> { VH_A1 } 87 % 100 % CSDL giao dịch nén, và Bảng định lượng 1 { B3 } ==> { A4 } 92 % 100 % 2 { A4 } ==> { B3 } 92 % 95 % 3 { E2 } ==> { A4 } 88 % 100 % 4 { A4 } ==> { E2 } 88 % 91 % 5 { E2 } ==> { B3 } 88 % 99 % 6 { B3 } ==> { E2 } 88 % 95 % 7 { B3, E2 } ==> { A4 } 87 % 100 % 8 { A4, E2 } ==> { B3 } 87 % 99 % 9 { A4, B3 } ==> { E2 } 87 % 95 % Bảng 2.10: Luật kết hợp thu được với độ hỗ trợ 90% và độ tin cậy 80% STT Luật kết hợp Đỗ hỗ trợ Độ tin cậy CSDL không nén 1 { LH_A2 } ==> { VH_A1 } 92 % 99 % 2 { VH_A1 } ==> { LH_A2 } 92 % 95 % CSDL giao dịch nén, không Bảng định lượng 1 { LH_A2 } ==> { VH_A1 } 92 % 100 % 2 { VH_A1 } ==> { LH_A2 } 92 % 95 % CSDL giao dịch nén, và Bảng định lượng 12 1 { B3 } ==> { A4 } 92 % 100 % 2 { A4 } ==> { B3 } 92 % 95 % 2.6. Kết luận Trong chương này luận án nghiên cứu ĐSGT và phát triển thuật toán nén CSDL giao dịch sử dụng cho bài toán khai phá luật kết hợp mờ. Với cách tiếp cận này, các giao dịch gần nhau được gộp lại để tạo thành giao dịch mới, làm giảm kích thước của CSDL đầu vào. Thuật toán nén CSDL giao dịch được thử nghiệm trên CSDL: FAM95 và STULONG. Kết quả thử nghiệm với 2 CSDL cho thấy phương pháp đề xuất nén CSDL cho kết quả nhanh hơn với phương pháp đề xuất trong [2] và giá trị của các tập phổ biến tìm được giống với khi chúng ta sử dụng CSDL không nén. Nội dung của chương này được công bố trong các công trình [i, ii]. Trong chương này, luận án sử dụng ĐSGT với các biểu diễn đơn thể hạt cho các thuộc tính với tham số giống nhau. Để nâng cao hiệu quả khai phá luật kết hợp và để tìm ra các luật có ý nghĩa hơn, trong chương 3 luận án nghiên cứu và đề xuất phương pháp tối ưu các tham số mờ cho phù hợp với từng thuộc tính với biểu diễn đơn thể hạt và đa thể hạt. 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 Trong chương này, luận án trình bày một số cách phân chia miền mờ và đề xuất phương pháp phân chia miền mờ bằng cách sử dụng lý thuyết ĐSGT dựa trên biểu diễn đơn thể hạt và đa thể hạt. ĐSGT cho phép mô hình hoá và thiết kế các từ ngôn ngữ cùng với ngữ nghĩa dựa trên tập mờ. Luận án đề xuất thuật toán tối ưu các hàm thuộc được xây dựng dựa trên lý thuyết ĐSGT cho bài toán khai phá luật kết hợp mờ. Các kết quả thực nghiệm cho thấy kết quả của các phương pháp đề xuất có một số ưu việt hơn một số phương pháp đã đề xuất trước đây. 3.1. Phân hoạch cho miền giá trị của thuộc tính 3.1.1. Đặt vấn đề Bài toán phân chia miền xác định các thuộc tính định lượng của một tập dữ liệu đầu vào như sau: Cho miền xác định của một thuộc tính (ở đây chỉ xét thuộc tính định lượng). Mỗi thuộc tính định lượng có một miền xác định (hoặc miền giá trị) là miền trên trục số thực bao gồm các giá trị mà thuộc tính định lượng đó có thể nhận. Yêu cầu là phải phân chia miền thuộc tính ra thành các hạt và mỗi hạt có nhãn ngôn ngữ biểu thị bằng tập mờ. Trong cách tiếp cận lý thuyết tập mờ, các tác giả phân chia miền giá trị của thuộc tính thành các tập mờ, và điều chỉnh tham số của các tập mờ. Việc gán nhãn ngôn ngữ vào các tập mờ dựa trên trực giác của người thiết kế. ĐSGT xuất phát từ khung nhận thức ngôn ngữ để từ đó thiết kế các từ ngôn ngữ cùng với ngữ nghĩa dựa trên tập mờ của chúng. 3.1.2. Rời rạc hóa thuộc tính định lượng Có 2 cách phân chia miền xác định thuộc tính thành các miền con rõ và mờ. Cách phân chia thành các miền con rõ có thể thấy qua ví dụ sau: Nếu A là thuộc tính định lượng rời rạc (quantitative & discrete) hoặc là thuộc tính hạng mục (categorical) với miền giá trị hữu hạn dạng {v1, v2, , vk} và k đủ bé thì ta sẽ biến đổi thuộc tính này thành k thuộc tính nhị phân dạng A_V1, A_V2, A_Vk. Giá trị của một bản ghi tại trường A_Vi bằng 1 nếu giá trị của bản ghi đó của thuộc tính A ban đầu bằng 𝑣𝑖, trong các trường hợp còn lại giá trị của A_Vi sẽ là 0. 13 Nếu A là thuộc tính định lượng liên tục (quantitative & continuous) hoặc A là thuộc tính định lượng rời rạc hay thuộc tính hạng mục với miền giá trị dạng {v1, v2, , vp} (p lớn) thì ta sẽ ánh xạ thành q thuộc tính nhị phân , , , < 𝐴: startq. . endq >. Giá trị của một bản ghi tại trường sẽ bằng 1 nếu giá trị của bản ghi đó tại thuộc tính A ban đầu năm trong khoảng [starti. . endi], ngược lại nó sẽ nhận giá trị 0. Trong bài toán khai phá luật kết hợp mờ, chúng ta cần phải phần chia miền giá trị của các thuộc tính thành các miền mờ, với mỗi miền mờ này thường gắn với một hàm thuộc và nhãn ngôn ngữ. Cách phân chia miền xác định thành các miền con mờ có nhiều ưu điểm hơn và sẽ là cách mà luận án sử dụng nên sẽ được trình bày kỹ ở mục 3.1.3. 3.1.3. Phân chia miền giá trị của thuộc tính theo cách tiếp cận lý thuyết tập mờ Một số phương pháp phân chia miền mờ phổ biến: a) Phân chia một cách ngẫu nhiên: Chọn một số cố định các miền cần chia và chia 1 mục thành các vùng đều nhau, phương pháp này đơn giản và có lẽ là tốt khi ta không có thông tin nào khác. b) Phân chia theo phương pháp phân cụm: Áp dụng phương pháp phân cụm để tìm kiếm tập mờ, phương pháp này tính đến sự đa dạng của việc phân bố dữ liệu. c) Phân chia theo phương pháp ràng buộc động Việc phân chia miền mờ giúp chúng ta xây dựng các hàm thuộc cho các miền mờ. Mỗi hàm thuộc thường có các tham số để điều chỉnh độ thuộc của các giá trị vào miền mờ. Tối ưu các tham số của các hàm thuộc là nhiệm vụ quan trọng trong bài toán khai phá luật kết hợp mờ. Để giải quyết nhiệm vụ này, một số nghiên cứu sử dụng thuật toán tiến hoá nhằm tăng khả năng trong việc tối ưu. 3.2. Phương pháp phân hoạch mờ bằng biểu diễn thể hạt với ĐSGT Trong phần này, luận án trình bày phương pháp phân chia miền xác định thuộc tính định lượng theo cách tiếp cận của Đại số gia tử dựa trên biểu diễn đơn thể hạt và đa thể hạt của dữ liệu. ĐSGT cho ta một cấu trúc toán học khá tốt xây dựng trên miền xác định thuộc tính, giúp ta không chỉ có được phân hoạch miền xác định một cách đơn giản mà còn cho phép gắn chặt ngữ nghĩa của miền con mờ với nhãn ngôn ngữ mà nó biểu diễn, luôn đảm bảo thứ tự tự nhiên của các nhãn ngôn ngữ đó. Không những thế, phân hoạch dựa trên ĐSGT theo cách luận án sử dụng luôn là một phân hoạch mạnh. Với cách tiếp cận này, các luật kết hợp được khai phá sẽ phản ánh phong phú và đa dạng hơn tri thức ẩn chứa trong kho thông tin được khai phá, từ những tri thức có tính khái quát cao cho đến những tri thức mang tính riêng biệt, chi tiết hơn đáp ứng tốt nhu cầu của người quản lý. 3.2.1. Phân hoạch giá trị miền thuộc tính sử dụng biểu diễn đơn thể hạt Với một số kết quả liên quan đến khoảng tính mờ của các phần tử của ĐSGT nêu trong mục 1.2.4, ta có thể thấy ngay một cách tính độ thuộc của một giá trị bất kỳ trong CSDL số đã cho vào các tập mờ dùng phân chia miền mờ của mục [25, 26]. Ta thấy, trên miền xác định của mục (item) (có thể đã chuẩn hóa về đoạn [0,1], một giá trị bất kỳ đều nằm giữa hai giá trị ĐLNN của 2 khoảng tính mờ liên tiếp hoặc trùng với một giá trị ĐLNN của một khoảng tính mờ do tính chất tạo nên phân hoạch miền xác định của các khoảng tính mờ. Như vậy, khoảng cách giữa giá trị 𝑥𝑖𝑗 đó tới 2 giá trị ĐLNN có thể dùng để tính độ thuộc của 𝑥𝑖𝑗 vào các tập mờ được biểu diễn bởi các khoảng tính mờ đó (trường hợp trùng với 1 giá trị ĐLNN thì chỉ có 1 độ thuộc): khoảng cách càng nhỏ thì độ thuộc càng lớn, nếu trùng có thể coi đạt 1. Trong Hình 3.1, tác giả dùng các giá trị ĐLNN để phân hoạch miền xác 14 định của thuộc tính thành các miền mờ. Tương ứng với mỗi miền mờ dựng các tam giác là biểu diễn các hàm thuộc của tập mờ với 1 đỉnh có tọa độ (𝜐(𝑥𝑖), 1), hai đỉnh còn lại nằm trên miền xác định, có tọa độ tương ứng là (𝜐(𝑥𝑖−1),0), (𝜐(𝑥𝑖+1), 0), trong đó 𝜐(𝑥𝑖−1), 𝜐(𝑥𝑖), 𝜐(𝑥𝑖+1) là 3 giá trị ĐLNN liên tiếp (Hình 3.1). Hình 3.1: Xây dựng phần hoạch miền xác định của thuộc tính theo cách tiếp cận ĐSGT Có thể thấy về thực chất hai cách xây dựng này là tương đương. Thật vậy, giả sử ta có điểm E là một điểm tùy ý trên trục biểu diễn miền xác định của thuộc tính 𝐼𝑖 . Khi đó, theo cách thứ nhất, khoảng cách 𝐸𝜈(𝑥2) và 𝐸𝜈(𝑥3) sẽ được dùng để xác định độ thuộc của E vào các tập mờ được biểu diễn bằng các hàm thuộc - tam giác 𝜈(𝑥1) 𝐵 𝜈(𝑥3) và 𝜈(𝑥2) 𝐶 𝜈(𝑥4), thông qua việc chuẩn hóa để độ thuộc luôn nằm trong khoảng [0,1]. Còn theo cách thứ 2, ta có EG và EF chính là độ thuộc của E vào 2 tập mờ này. Ta có, do EG song song với 𝜈(𝑥2) 𝐵 nên 𝐸𝐺 𝜈(𝑥2)𝐵 = 𝐸 𝜈(𝑥3) 𝜈(𝑥2)𝜈(𝑥3) . Tương tự 𝐸𝐹 𝑣(𝑥3)𝐶 = 𝜈(𝑥2)𝐸 𝜈(𝑥2)𝜈(𝑥3) . Ngoài ra, 𝜈(𝑥2) 𝐵 = 𝜈(𝑥3) 𝐶 = 1 nên cuối cùng ta có 𝐸𝐹 𝐸𝐺 = 𝐸 𝜈(𝑥2) 𝐸 𝜈(𝑥3) . Từ đó dễ dàng suy ra thực chất hai cách gắn độ thuộc này là tương đương. Điều đó cũng nhấn mạnh thêm cách gắn độ thuộc theo cách của ĐSGT là hợp lý về mặt cảm nhận. Cách xây dựng các hàm thuộc hay tương đương là các tập mờ để phân chia miền xác định của thuộc tính theo cách tiếp cận ĐSGT như trên có những ưu điểm sau: - Do cách xây dựng sử dụng ĐSGT có cơ sở phù hợp với ngữ nghĩa con người cảm nhận nên về mặt cảm tính, có thể thấy các hàm thuộc được xây dựng là phản ánh khá tốt ngữ nghĩa của tập mờ mà nó biểu diễn. - Dễ thấy là độ phủ của các hàm thuộc là tốt (luôn phủ kín miền xác định). Từ đó ta thấy nếu cần tối ưu mức độ phù hợp phù hợp của MF, ta chỉ cần tối ưu mức độ chồng lên nhau và mức độ bao phủ của các MF. Bài toán tối ưu các tham số của ĐSGT theo độ chồng lấn và tính hữu dụng có thể giải bằng một giải thuật GA. - Các tham số cần quản khi xây dựng là ít (mỗi tam giác một tham số, là giá trị ĐLNN), khi thay đổi tham số ban đầu của ĐSGT, dễ dàng xác định lại được các MF mới và các MF vẫn giữ nguyên độ đo chồng lấn và phủ như cũ. Phương pháp này đơn giản và hợp lý. 3.2.2. Phân hoạch giá trị miền thuộc tính sử dụng biểu diễn đa thể hạt Phương pháp phân chia miền mờ theo tiếp cận ĐSGT sử dụng biểu diễn đơn thể hạt tuy có những ưu điểm như đã trình bày, vẫn còn có những hạn chế liên quan đến ngữ nghĩa của dữ liệu. Theo lý thuyết ĐSGT, các MF mà ta tạo nên ở trên dựa trên phân hoạch của các hạng từ có cùng độ dài. Điều đó có nghĩa các luật kết hợp mà ta khai phá được chỉ bao gồm các hạng từ có cùng độ dài, mà điều đó làm giảm ý nghĩa của các luật khai phá được. Nếu ta không quan tâm lắm đến ngữ nghĩa dữ liệu, chỉ đơn thuần là phân chia miền xác định một cách gần như máy móc (như phần lớn các Hình 3.2: Phân hoạch miền giá trị của thuộc tính dựa trên biểu diễn đơn thể hạt 15 phương pháp theo cách tiếp cận tập mờ đã làm) thì phương pháp đề xuất sử dụng biểu diễn đơn thể hạt sử dụng ĐSGT trình bày trong mục 3.2.1 là khá tốt. Tuy nhiên, nếu để ý đến ngữ nghĩa của dữ liệu - là điều cực kỳ quan trọng để có được các tri thức tốt trong khai phá luật kết hợp - ta phải có một cách tiếp cận sâu hơn. Có thể xây dựng các khoảng mờ ngữ nghĩa để tạo nên các phân hoạch của các hạng từ có độ dài khác nhau nhưng cách này không thật chuẩn tắc vì những phân hoạch tạo ra không phải là duy nhất. Trong chương này, luận án chọn cách tiếp cận dựa trên biểu diễn dữ liệu theo cấu trúc đa thể hạt. Với phương pháp này, nhằm nâng cao tri thức của các luật kết hợp, các luật kết hợp thu được sẽ phong phú hơn. Hình 3.3: Cấu trúc hạt thể nhiều mức Về mặt tư tưởng, sử dụng biểu diễn đa thể hạt, như đã nói, cho ta cái nhìn đa dạng hơn về thông tin đầu vào. Việc xây dựng, biểu diễn và sử dụng cấu trúc hạt thường tuân thủ quy tắc đa mức và đa dạng (multilevel và multiview). Quy tắc multilevel là ưu điểm do cấu trúc hạt mang lại thể hiển ở sự hiểu và biểu diễn đa mức các hạt. Quy tắc đa dạng gắn liền vừa với sự tồn tại khách quan của dữ liệu (các hạt thông tin) vừa với cái nhìn chủ quan của người nghiên cứu sử dụng dữ liệu, theo đó ở mỗi mức cấu trúc hạt, thông tin có thể phân chia theo các cách khác nhau. Với tính toán hạt tuân thủ hai quy tắc nêu trên, chúng ta có cái nhìn có cấu trúc về dữ liệu, vừa mang tính hệ thống lại vừa đơn giản hơn trong việc giải các bài toán khai phá dữ liệu. Ngoài ra, rất quan trọng trong hướng nghiên cứu theo tiếp cận của ĐSGT của luận án, tính toán hạt và gắn liền với nó là biểu diễn đa thể hạt dữ liệu theo các quy tắc nêu trên thỏa mãn những đòi hỏi về tính diễn giải được. Các đòi hỏi đó là việc phân chia các hạt cần bảo toàn thứ tự ngôn ngữ tự nhiên (thí dụ như “trẻ” < “già” thì khi phân chia tiếp, mọi phần của nhãn ngôn ngữ “trẻ”, chẳng hạn “khá trẻ” phải nhỏ hơn mọi phần của “trung niên”, chẳng hạn “khá già”, tức “khá trẻ” < “khá già” và bảo toàn quan hệ chung-riêng, từ tính chung cao hơn thì giá tập mờ của nó chứa giá tập mờ của từ có tính riêng hơn; đa thể hạt là cấu trúc có thể thỏa mãn cả hai đòi hỏi này. Một điểm nhấn quan trọng là với cách tiếp cận của ĐSGT, việc chuyển sang tính toán hạt đa mức và đa dạng hoàn toàn đơn giản mà luận án sẽ chứng tỏ ở sau. Đối với lý thuyết tập mờ (theo L.Zadeh), một trong những hạn chế của các phương pháp sử dụng biểu diễn đa thể hạt là đôi khi lựa chọn các hàm thuộc không dễ dàng vì có ít cơ sở để xác định các hàm thuộc ở các mức khác nhau, và chưa thể xây dựng ràng buộc giữa chúng. Hầu như việc xác định này chỉ tiến hành theo kinh nghiệm, qua ví dụ trên ta cũng có thể cảm nhận được điều đó. Đồng thời, việc tiến hành tính toán với các mức khác nhau của dữ liệu sẽ gây sự phức tạp kéo theo chi phí lớn hơn nhiều về thời gian cũng như bộ nhớ. Ngược lại, với ĐSGT việc thiết kế phân hoạch mờ trên miền giá trị của thuộc tính các mức khác nhau của biểu diễn đa thể hạt là dễ dàng vì nằm trong bản thân cách xây dựng ĐSGT. Trong lý thuyết Hình 3.4: Phân hoạch miền giá trị của thuộc tính dựa trên biểu diễn đa thể hạt 16 ĐSGT, với mỗi miền giá trị của thuộc tính chỉ cần xác định bộ tham số mờ của ĐSGT là ta có thể xác định khoảng tính mờ của tất cả các hạng từ thông qua các công thức tính toán xác định dù cho hạng từ này có độ dài bao nhiêu (tức dù cho hạng từ này có nằm ở mức bao nhiêu trong hệ thống biểu diễn đa thể hạt). Tính phân cấp là một trong những cách thức chính mà GrC sử dụng cũng nằm trong cách xây dựng ĐSGT. Theo lý thuyết ĐSGT, mỗi hạng từ x có độ dài k có thể phân hoạch thành các hạng từ ℎ𝑖𝑥 (với ℎ𝑖 là mọi gia tử của ĐSGT đang xét) có độ dài k+1. Có thể nói, ĐSGT là công cụ hết sức thích hợp cho tính toán đa thể hạt. Hình 3.4 là một ví dụ gồm 3 thể hạt được xây dựng dựa trên giá trị định lượng nghữ nghĩa của ĐSGT. Thể hạt mức 0 gồm 3 hàm thuộc, thể hạt mức 1 gồm 4 hàm thuộc, và thể hạt mức 2 gồm 6 hàm thuộc. 3.3. Phương pháp tối ưu tham số mờ ĐSGT cho bài toán khai phá luật kết hợp Để tìm kiếm hàm thuộc tối ưu cho bài toán khai phá luật kế hợp mờ, các tác giả trước đây đã sử dụng một số tiêu chí để đánh giá các hàm thuộc cho các thuộc tính. Cụ thể, sự thích hợp (Suitabitity) của tập MF dùng để phân chia thuộc tính ngôn ngữ 𝐼𝑞 có thể đánh giá qua 3 yếu tố: độ chồng lấn (Overlap_factor) đo độ chồng lấn của các MF lên nhau; độ phủ (Coverge factor) đo độ bao phủ miền giá trị của các MF này, và tính hữu dụng (usage factor). Trong phần này, dựa vào giá trị định lượng ngữ nghĩa của ĐSGT để xây dựng các hàm thuộc cho các thuộc tính số và áp dụng cho bài toán khai phá luật kết hợp mờ. Thay vì đi tối ưu các tham số của hàm thuộc, chúng ta đi tối ưu các tham số mờ của ĐSGT. Hình 3.5: Lược đồ tìm kiếm phân hoạch tối ưu cho miền xác định thuộc tính và khai phái luật kết hợp Hình 3.5 là lược đồ tìm kiếm hàm thuộc và khai phá luật kết hợp gồm hai bước: Bước 1: Tìm kiếm hàm thuộc: với các tham số ĐSGT của các thuộc tính. Chúng ta có thể dễ dàng xây dựng các hàm thuộc cho các thuộc tính