Tóm tắt Luận án Tiến sĩ Toán học: 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

Chia sẻ: Trần Trung Hiếu | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

42
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu chính của luận văn là nghiên cứu các phương pháp biểu thị ngữ nghĩa các khái niệm mờ (các từ ngôn ngữ mờ) thông qua hàm thuộc (tập mờ) hoặc các phương pháp toán học khác sao cho nó biểu thị ngữ nghĩa các khái niệm phù hợp nhất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Toán học: 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

VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ NGUYỄN TUẤN ANH 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 Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2020
Công trình được hoàn thành 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 Người hướng dẫn khoa học 1: PGS. TSKH Nguyễn Cát Hồ Người hướng dẫn khoa học 2: TS Trần Thái Sơn Phản biện 1: PGS.TS. Trần Đình Khang Phản biện 2: PGS.TS. Nguyễn Hải Châu Phản biện 3: TS. Phạm Thanh Hà Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp 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 vào hồi … giờ …, ngày … tháng … năm … Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và công nghệ - Thư viện Quốc gia Việt Nam
CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN [1]. Trần Thái Sơn, Nguyễn Tuấn Anh, “Nâng cao hiệu quả khai phá luật kết hợp mờ theo hướng tiếp cận đại số gia tử", Kỷ yếu hội nghị quốc gia lần VI về nghiên cứu cơ bản và ứng dụng công nghệ thông tin (Fair) - Huế, 6/2013. [2]. Tran Thai Son, Nguyen Tuan Anh, “Improve efficiency fuzzy association rule using hedge algebra approach, Journal of Computer Science and Cybernetics, Vol 30, No 4, 2014. [3]. Tran Thai Son, Nguyen Tuan Anh, Hedges Algebras and fuzzy partition problem for qualitative attributes, Journal of Computer Science and Cybernetics, V.32, N.4, 2016. [4]. Tran Thai Son, Nguyen Tuan Anh, Partition fuzzy domain with multi- granularity representation of data based on Hedge Algebra approach, Journal of Computer Science and Cybernetics, vol. 33, pp. 63-76, 2017.
1 MỞ ĐẦU Bài toán khai thác luật kết hợp là hướng nghiên cứu quan trọng và sớm được nghiên cứu phát triển trong hướng nghiên cứu khai phá dữ liệu. Trong những năm gần đây nhiều giải thuật đã được được phát triển theo nhiều hướng khác nhau nhưng chủ yếu xoay quanh hai hướng chính: (i) Cải tiến tốc độ trung bình các thuật toán khai phá luật vì thông thường, đây là bài toán có độ phức tạp hàm mũ do phải quét CSDL nhiều lần. (ii) Nghiên cứu sâu hơn về ý nghĩa của các luật khai phá vì ta thấy không phải luật được khai phá nào cũng có ý nghĩa đối vời người sử dụng. Luật kết hợp mờ có dạng: Luật kết hợp mờ có dạng: “Nếu X là A Thì Y là B”. “X là A” gọi là tiền (tiên) đề, “Y là B” gọi là kết luận của luật. 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑝 }, Y= {𝑦1 , 𝑦2 , … , 𝑦𝑞 } là tập mục là tập con của tập thuộc tính I của CSDL. 𝐴 = {𝑓𝑥1 , 𝑓𝑥2 , … , 𝑓𝑥𝑝 }, B= {𝑓𝑦1 , 𝑓𝑦2 , … , 𝑓𝑦𝑞 } là các tập mờ tương ứng của các thuộc tính X, Y. Phân chia miền xác định của thuộc tính là bước khởi đầu quan trọng cho cả một quá trình xử lý thông tin. Gần đây, các nhà nghiên cứu đã chú ý đến việc nghiên cứu xây dựng các tập hàm thuộc như vậy vì thấy rõ tầm ảnh hưởng của công đoạn này lên công đoạn tiếp theo. Luận án nghiên cứu các phương pháp khai phá tri thức dạng luật kết hợp mờ với thông tin ngôn ngữ (luật dạng ngôn ngữ) từ các CSDL hay các kho dữ liệu số. Chúng tôi sử dụng Đại số gia tử (ĐSGT) thay cho lý thuyết tập mờ để nghiên cứu một số vấn đề về khai phá luật kết hợp: (i) Luật kết hợp mờ được nghiên cứu còn một số nhược điểm kể cả trong việc xây dựng thuật toán nhằm tăng tốc độ xử lý cũng như trong bài toán phân hoạch mờ miền xác định của thuộc tính nằm đưa ra các luật kết hợp có ý nghĩa. (ii) Với biểu diễn dữ liệu khác nhau, ĐSGT cho một cách tiếp cận thống nhất đơn giản mà có hiệu quả cao trong xử lý. Mục đích nghiên cứu: - Nghiên cứu các phương pháp biểu thị ngữ nghĩa các khái niệm mờ (các từ ngôn ngữ mờ) thông qua hàm thuộc (tập mờ) hoặc các phương pháp toán học khác sao cho nó biểu thị ngữ nghĩa các khái niệm phù hợp nhất. - Nghiên cứu các phương pháp khai phá tri thức nói chung và các luật mờ nói riêng. - Nghiên cứu các cách biểu diễn dữ liệu khác nhau của thông tin để có thể khai phá luật kết hợp một cách đa dạng, mang nhiều ý nghĩa. Luận án sử dụng biểu diễn dữ liệu đơn thể hạt và đa thể hạt, phù hợp với sự chú ý ngày càng gia tăng của hướng nghiên cứu này. CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ 1.1. Tập mờ và các phép toán trên tập mờ 1.1.1. Tập mờ (fuzzy set) Định nghĩa 1.1: Cho U là vũ trụ các đối tượng. Tập mờ A trên U là tập các cặp có thứ tự (𝑥, 𝜇𝐴 (𝑥)), với 𝜇𝐴 (𝑥) là hàm từ U vào [0, 1] gán cho mỗi phần tử x thuộc U giá trị 𝜇𝐴 (𝑥) phản ảnh mức độ thuộc của x thuộc vào tập mờ A. 1.1.2. Biến ngôn ngữ 1.1.3. Phân hoạch mờ Chúng ta có định nghĩa phân hoạch mờ như sau:
2 1) Định nghĩa 1.3: Cho m điểm cố định 𝑝1 , 𝑝2 , … , 𝑝𝑚 thuộc tập 𝑈 = [𝑎, 𝑏] ⊂ 𝑅 là không gian tham chiếu của biến cơ sở 𝑢 của biến ngôn ngữ 𝑋. Khi đó một tập 𝑇 gồm m tập mờ 𝐴1 , 𝐴2 , … , 𝐴𝑚 định nghĩa trên 𝑈 (với hàm thuộc tương ứng là 𝜇𝐴1 , 𝜇𝐴2 ,..., 𝜇𝐴𝑚 ) được gọi là một phân hoạch mờ của 𝑈 nếu các điều kiện sau thoả mãn, ∀𝑘 = 1, … , 𝑚:𝜇𝐴𝑘 (𝑝𝑘 ) (𝑝𝑘 thuộc về phần được gọi là lõi của 𝐴𝑘 ); 2) Nếu x ∉ [𝑝𝑘−1 , 𝑝𝑘+1 ] thì 𝜇𝐴𝑘 (𝑥) = 0 3) 𝜇𝐴𝑘 (𝑥) liên tục; 4) 𝜇𝐴𝑘 (𝑥) đơn điệu tăng trên [𝑝𝑘−1 , 𝑝𝑘 ]; 5) ∀𝑥 ∈ 𝑈, ∃𝑘, sao cho 𝜇𝐴𝑘 (𝑥) > 0; Nếu phân hoạch mờ thoả mãn thêm điều kiện 6) dưới đây thì được gọi là phân hoạch mờ mạnh. 6) ∀𝑥𝜖𝑈, ∑𝑚 𝑘=1 𝜇𝐴𝑘 (𝑥) = 1; Nếu phân hoạch mờ thoả mãn thêm điều kiện 7), 8), 9) dưới đây thì được gọi là phân hoạch đều. 7) Với 𝑘 ≠ 𝑚 thì ℎ𝑘 = 𝑝𝑘+1 − 𝑝𝑘 = hằng số 8) Các tập mờ 𝜇𝐴𝑘 (𝑥) là hàm đối xứng 1.2. Các tập mờ 𝝁𝑨𝒌 (𝒙) có cùng một dạng hình họcĐại số gia tử 1.2.1. Khái niệm Đại số gia tử Định nghĩa 1.4: Một ĐSGT được ký hiệu là bộ 4 thành phần được ký hiệu 𝐴𝑋 = (X, G, H, ≤) trong đố G là tập các phần tử sinh, H là tập các gia tử (hedge) còn " ≤ " là quan hệ cảm sinh ngữ nghĩa trên X. Giả thiết trong G có chứa các phần tử hằng 0, W, 1 với ý nghĩa là phần tử bé nhất, phần tử lớn nhất và phần tử trung hoà (neutral) trong X. Ta gọi mỗi giá trị ngôn ngữ 𝑥 ∈ 𝑋 là một hạng từ trong ĐSGT. Tập H gồm H − = {ℎ−1 < ℎ−2 < ⋯ < ℎ−𝑞 } và 𝐻 + = {ℎ1 < ℎ2 < ⋯ < ℎ𝑝 }. 1.2.2. Định lượng ngữ nghĩa của giá trị ngôn ngữ Định nghĩa 1.5: Cho AX = (𝑋, 𝐺, 𝐻, ≤) là một ĐSGT tuyến tính. Ánh xạ 𝑣𝔵 : 𝑋 → [0,1] được gọi là một hàm định lượng ngữ nghĩa của AX nếu: (i) 𝑣𝔵 là ánh ạ 1-1 từ tập X vào đoạn [0,1] và bảo toàn thứ tự trên X, tức là ∀𝑥, 𝑦 ∈ X, 𝑥 < 𝑦 ⇒ 𝑣𝔵 (𝑥) < 𝑣𝔵 (𝑦) và 𝔳𝔵 (0) = 0, 𝔳𝔵 (1) = 1. (ii) 𝑣(𝑿) liên tục: trù mật trong [0,1], nghĩa là ∀(𝑎, 𝑏) ≠ ∅ và (𝑎, 𝑏) ⊆ [0,1], (𝑎, 𝑏) ∩ 𝑣𝔵 (𝑿) ≠ ∅. Định nghĩa 1.6: Một hàm dấu 𝑆𝑖𝑔𝑛 ∶ X  {−1,0,1} là một ánh xạ được định nghĩa đệ qui như sau, trong đó ℎ, ℎ′  H và 𝑐  {𝒄− , 𝒄+ }: (1) 𝑆𝑖𝑔𝑛(𝑐 − ) = −1, 𝑆𝑖𝑔𝑛(𝑐 + ) = 1; (2) 𝑆𝑖𝑔𝑛(ℎ𝑐) = −𝑆𝑖𝑔𝑛(𝑐) nếu h âm đối với c; 𝑆𝑖𝑔𝑛(ℎ𝑐) = 𝑆𝑖𝑔𝑛(𝑐) nếu h dương đối với c; (3) 𝑆𝑖𝑔𝑛(ℎ′ℎ𝑥) = −𝑆𝑖𝑔𝑛(ℎ𝑥), nếu ℎ′ℎ𝑥  ℎ𝑥 và ℎ′ âm đối với ℎ; 𝑆𝑖𝑔𝑛(ℎ′ℎ𝑥) = 𝑆𝑖𝑔𝑛(ℎ𝑥), nếu ℎ′ℎ𝑥  ℎ𝑥 và ℎ′ dương đối với ℎ; (4) 𝑆𝑖𝑔𝑛(ℎ′ℎ𝑥) = 0, nếu ℎ′ℎ𝑥 = ℎ𝑥. Định nghĩa 1.7: Cho AX là một ĐSGT tuyến tính đầy đủ và 𝑓𝑚 là một độ đo tính mờ trên X. Ta nói ánh xạ 𝔳𝔵 : 𝑋  [0,1] được cảm sinh bởi độ đo tính mờ 𝑓𝑚 nếu được định nghĩa bằng đệ qui như sau: (1) 𝑣𝔵 (𝑊) =  = 𝑓𝑚(𝑐 − ), 𝑣𝔵 (𝑐 − ) =  – . 𝑓𝑚(𝑐 − ) = . 𝑓𝑚(𝑐 − ), 𝑣(𝑐 + ) =  + . 𝑓𝑚(𝑐 + );
3 𝑖−𝑠𝑖𝑔𝑛(𝑗) (2) 𝑣𝔵 (ℎ𝑗 𝑥) = 𝑣𝔵 (𝑥) + 𝑆𝑖𝑔𝑛(ℎ𝑗 𝑥) {∑𝑖=𝑠𝑖𝑔𝑛(𝑗) 𝜇(ℎ𝑖 )𝑓𝑚(𝑥) − 𝜔(ℎ𝑗 𝑥)𝜇(ℎ𝑗 )𝑓𝑚(𝑥)}, 1 với mọi j, −𝑞 ≤ 𝑗 ≤ 𝑝 và 𝑗  0, trong đó 𝜔(ℎ𝑗 𝑥) = [1 + 𝑆𝑖𝑔𝑛(ℎ𝑗 𝑥) 𝑆𝑖𝑔𝑛(ℎ𝑝 ℎ𝑗 𝑥) (𝛽 − 2 𝛼)] ∈ {𝛼, 𝛽}; 1.3. Bài toán khai phá luật kết hợp 1.3.1. Một số khái niệm Cho 𝐼 = {𝐼1 , 𝐼2 , . . , 𝐼𝑚 } là tập hợp của m tính chất riêng biệt. Giả sử D là CSDL, với các bản ghi chứa một tập con T các tính chất, các bản ghi đều có chỉ số riêng. Một luật kết hợp là một mệnh đề kéo theo có dạng 𝑋 → 𝑌, trong đó 𝑋, 𝑌 ⊆ 𝐼, thỏa mãn điều kiện 𝑋 ∩ 𝑌 = ∅. Các tập hợp X và Y được gọi là các tập hợp itemset. Định nghĩa 1.10: Một luật kết hợp là một mệnh đề kéo theo có dạng 𝑋 → 𝑌, trong đó 𝑋, 𝑌  𝐼 trong đó X và Y được gọi là các tập mục (itemsets), thỏa mãn điều kiện 𝑋 ∩ 𝑌 = ∅. Tập X gọi là nguyên nhân, tập Y gọi là hệ quả. Có 2 độ đo quan trọng đối với luật kết hợp: Độ hỗ trợ và độ tin cậy. Định nghĩa 1.11: Độ hỗ trợ của tập mục X: Đỗ hỗ trợ của tập mục X là tỷ lệ giữa số lượng các bản ghi trong D chứa tập mục X với số bản ghi trong D. |𝑋| (1.1) 𝑆𝑢𝑝𝑝(𝑋) = |𝐷| Định nghĩa 1.12: Độ hỗ trợ của luật 𝑋 → 𝑌: Độ hỗ trợ của một luật kết hợp 𝑋 → 𝑌 là tỷ lệ giữa số lượng các bản ghi chứa tập hợp 𝑋 ∪ 𝑌, so với tổng số các bản ghi trong D. |𝑋∪𝑌| (1.2) 𝑆𝑢𝑝𝑝(𝑋 → 𝑌) = 𝑃(𝑋 ∪ 𝑌) = |𝐷| Định nghĩa 1.13: Độ tin cậy của luật 𝑋 → 𝑌: Độ tin cậy của một luật kết hợp 𝑋 → 𝑌 là tỷ lệ giữa số lượng các bản ghi trong D chứa 𝑋 ∪ 𝑌 với số bản ghi trong D chứa tập hợp X. 𝑆𝑢𝑝𝑝(𝑋 ∪ 𝑌) (1.3) 𝑐𝑜𝑛𝑓(𝑋 → 𝑌) = 𝑆𝑢𝑝𝑝(𝑋) 1.3.2. Bài toán luật kết hợp mờ Cho 𝐷𝑇 = {𝑡1 , 𝑡2 , … , 𝑡𝑛 } là CSDL giao dịch, n là tổng số bản ghi trong D. Cho 𝐼 = {𝑖1 , 𝑖2 , … , 𝑖𝑚 } là các mục, với mỗi mục 𝑖𝑗 (1 ≤ 𝑗 ≤ 𝑚) là thuộc tính hạng mục hoặc thuộc tính định lượng. Một tập thuộc tính mờ là một cặp 〈𝑍, 𝐶〉 với Z tương ứng là tập các thuộc tính zj và C tương ứng là tập các tập mờ 𝑐𝑗 . Nếu luật kết hợp mờ 𝑋 𝑖𝑠 𝐴 ⇒ 𝑌 𝑖𝑠 𝐵 gọi là tin cậy nếu thảo mãn độ hỗ trợ 𝐹(𝑍,𝐶) và độ tin cậy 𝐹𝐶((𝑋,𝐴),(𝑌,𝐵)) , với 𝑍 = 𝑋 ∪ 𝑌, 𝐶 = 𝐴 ∪ 𝐵. Độ hỗ trợ mờ của tập mục 〈𝑍, 𝐶〉 ký hiệu là 𝑓𝑠(〈𝑍, 𝐶〉) được xác định theo công thức: ∑𝑛𝑖=1 ∏𝑚 𝑖 𝑗=1(𝑡 [(𝑥𝑗 , 𝑎𝑗 )]) (1.4) 𝑓𝑠(〈𝑍, 𝐶〉) = 𝑛 Trong đó m là số lương tập mục trong tập mục (𝑍, 𝐶). Độ tin cậy mờ được xác định theo công thức sau: 𝑓𝑠(𝑍, 𝐶) 𝐹𝐶((𝑋,𝐴),(𝑌,𝐵)) = (1.5) 𝑓𝑠(< 𝑋, 𝐴 >) Thuật toán khai phá luật kết hợp mờ dựa trên thuật toán Apriori: Thuật toán khai phá luật kết hợp mờ được chia làm hai pha như sau: Pha 1: Tìm tất cả các tập thuộc tính mờ phổ biến dạng 〈𝑍, 𝐶〉 có độ hỗ trợ lớn hơn độ hỗ trợ cực tiểu của người dùng nhập vào: 𝑓𝑠(〈𝑍, 𝐶〉) ≥ 𝑓𝑚𝑖𝑛𝑠𝑢𝑝
4 Pha 2: Sinh các luật kết hợp mờ tin cậy từ các tập phổ biến đã tìm thấy ở pha thứ nhất. Pha này đơn giản và tốn kém ít thời gian hơn so với pha trên. Nếu 〈𝑍, 𝐶〉 là một tập thuộc fc tính mờ phổ biến thì luật kết hợp được sinh ra từ X có dạng: Z ′ is C ′ → Z\Z ′ is C\C ′. Với Z' là tập con khác rỗng của Z, Z\Z' là hiệu của hai tập hợp, C' là tập con khác rỗng của C và là tập các tập mờ tương ứng với các thuộc tính trong Z', C\C' là hiệu hai tập hợp, 𝑓𝑐 là độ tin cậy của luật thỏa mãn: 𝑓𝑐 ≥ 𝑓𝑚𝑖𝑛𝑐𝑜𝑛𝑓. 1.4. Kết luận Trong chương này, luận án đã tóm tắt những kiến thực cơ sở làm nền tảng phục vụ trong quá trình nghiên cứu. Nó bao gồm những nội dung chính sau: - Lý thuyết tập mờ bao gồm các khái niệm tập mờ, phương pháp xây dựng tập mờ, biến ngôn ngữ, phân hoạch mờ,... - Hệ thống lý thuyết về ĐSGT với những khái niện nền tảng như: ĐSGT, ĐSGT tuyến tính, ĐSGT tuyến tính đầy đủ, độ đo tính mờ của gia tử, phần tử sinh, phương pháp xác định giá trị định lượng của từ ngôn ngữ, khoảng tính mờ,... - Một số khái niệm cơ bản về luật kết hợp, luật kết hợp mờ và một số hướng nghiên cứu về khai phá luật kết hợp mờ. - Với những kiến thức cơ sở đã được trình bày trong chương trình là nền tảng đủ để thực hiện các mục tiêu đã đặt ra của luận án. 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Ử Trong chương này luận án đề xuất ứng dụng ĐSGT và đề xuất giải pháp nén CSDL giao dịch mờ nhằm tạo ra CSDL giao dịch mới có kích thước nhỏ hơn. Với phương pháp này giúp tìm ra các luật kết hợp mờ dạng ngôn ngữ gần gũi với con người và giảm thời gian khai phá luật kết hợp. 2.1. Đặt vấn đề Gần đây, các thuật toán sử dụng cách nén dữ liệu trong CSDL nhị phân cung cấp một giải pháp tốt có thể giảm yêu cầu không gian lưu trữ và thời gian xử lý dữ liệu. Jia - Yu Dai (2008) đã đề xuất thuật toán nén CSDL giao dịch nhị phân gọi là M2TQT. Ý tưởng cơ bản của thuật toán này là: gộp các giao dịch có quan hệ gần nhau để tạo thành giao dịch mới, kết quả thu được là tạo ra CSDL mới có kích thước nhỏ hơn, có thể giảm thời gian xử lý dữ liệu, giảm không gian lưu trữ. Thuật toán M2TQT được đánh giá là tốt hơn các phương pháp đã đề xuất trước đây. Tuy nhiên thuật toán M2TQT chỉ thực hiện với CSDL nhị phân. Nhằm nâng cao hiệu quả khai phá luật kết hợp, luận án đề xuất phương pháp khai phá luật kết hợp mờ theo cách tiếp cận ĐSGT, sử dụng cách nén dữ liệu cho một CSDL bất kỳ. 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 (chiều ngang) của CSDL đầu vào. Thực nghiệm cho thấy, cách tiếp cận này cho kết quả tốt hơn các cách tiếp cận đã có. Nội dung chương này, luận án trình bày cách thức mờ hóa các thuộc tính mờ theo hướng tiếp cận ĐSGT, thuật toán nén CSDL mờ, và thuật toán khai phá luật kết hợp mờ với CSDL nén. 2.2. Khai phá luật kết hợp mờ theo hướng tiếp cận ĐSGT 2.2.1. Mờ hóa cơ sở dữ liệu giao dịch Với cách tiếp cận ĐSGT, các giá trị hàm thuộc của mỗi giá trị của CSDL được tính theo cách như sau. Trước hết, miền giá trị mỗi thuộc tính mờ được xem là một ĐSGT. Với bài toán khai phá luật kết hợp mờ sử dụng lý thuyết tập mờ, chúng ta các phải xây dựng các
5 hàm thuộc cho mỗi thuộc tính. Sau đó, dựa vào hàm thuộc đã xây dựng để tính độ thuộc của các giá trị và các miền mờ tương ứng. Luận án đề xuất mỗi thuộc tính định lượng sẽ sử dụng một cấu trúc ĐSGT. Dựa vào giá trị định lượng ngữ nghĩa của các phần tử của ĐSGT, chúng ta xây dựng lên các phân hoạch mờ để tính độ thuộc của các phần tử trong CSDL đến các miền mờ. Bước 1: Chuẩn hóa các giá trị của các thuộc tính mờ về đoạn [0,1]. Bước 2: Xét các miền mờ 𝑠𝑗 của thuộc tính 𝑥𝑖 là các phần tử của ĐSGT 𝐴𝑋𝑖 . Khi đó, x một giá trị bất kỳ dj i của 𝑥𝑖 đều nằm giữa 2 giá trị định lượng ngữ nghĩa nào đó của 2 phần x tử của 𝐴𝑋𝑖 . Khoảng cách trên đoạn [0,1] giữa dj i và giá trị định lượng ngữ nghĩa của hai x x phần tử gần dj i nhất về hai phía có thể dùng để xác định độ gần gũi của dj i vào hai miền mờ (hai phần tử của ĐSGT). Độ x gần gũi giữa dj i với các phần tử khác của ĐSGT được xác định bằng 0. Để xác định độ thuộc cuối cùng, ta phải chuẩn hóa (chuyển về giá trị trong đoạn [0,1] rồi lấy 1 trừ khoảng cách đã chuẩn hóa đó). Ta sẽ có, ứng với mỗi giá trị Hình 2.1: Xây dựng phân hoạch mờ dựa trên x dj i một cặp độ thuộc. ĐSGT xi Như vậy để tính độ thuộc dj của thuộc tính 𝑥𝑖 vào miền mờ 𝑠𝑗 : x x 𝜇𝑠𝑗 (dj i ) = 1 − | 𝑣(𝑠𝑗 ) − dj i |, với 𝑣(𝑠𝑗 ) là giá trị định lượng ngữ nghĩa của phần tử 𝑠𝑗 . Bảng 2.1: Cơ sở dữ liệu ví dụ Chúng ta có các giá trị được mờ hóa như trong TID A B Bảng 2.2. 𝑇1 30 40 Ký hiệu: A1, B1: Very Low; A2, B2: Least Low; 𝑇2 41 48 A3, B3: Least Heigh, A4, B4: Very Heigh; 𝑇3 45 32 Bảng 2.2: Mờ hóa dữ liệu trong Bảng 2.1 A B TID A1 A2 A3 A4 B1 B2 B3 B4 𝑇1 0.825 0.925 0 0 0 0.975 0.775 0 𝑇2 0 0.965 0.785 0 0 0.895 0.855 0 𝑇3 0 0.925 0.825 0 0.805 0.945 0 0 Ví dụ 2.1: Cho CSDL ví dụ như trong Bảng 2.1 gồm có hai thuộc tính A và B. ĐSGT sử dụng cho hai thuộc tính này có cấu trúc giống nhau: 𝐴𝑋 = (𝑋, 𝐺, 𝐻, ≤), 𝐶 − = {𝐿𝑜𝑤}, 𝐶 + = {𝐻𝑖𝑔ℎ𝑡}, 𝐻 − = {𝐿𝑒𝑎𝑠𝑡}, 𝐶 + = {𝑉𝑒𝑟𝑦}, các tham số như sau: 𝑓𝑚(𝐿𝑜𝑤) = 𝑓𝑚(𝐻𝑖𝑔ℎ𝑡) = 0.5, 𝜇(𝑉𝑒𝑟𝑦) = 𝜇(Least) = 0.5, 𝐷𝑜𝑚(𝐴, 𝐵) = [0, 100]. Khi đó ta tính được các giá trị định lượng ngữ nghĩa: v(Very Low) = 0.125, v(Least Low) = 0.375, v(Least Height) = 0.625, v(Very Height) = 0.875. 2.2.2. Quan hệ khoảng cách giao dịch Dựa vào khoảng cách giữa các giao dịch, có thể gộp các giao dịch có khoảng cách gần nhau để tạo ra nhóm giao dịch, kết quả là thu được CSDL mới có kích thước nhỏ hơn. Quan hệ giao dịch và quan hệ khoảng cách giao dịch cho các giao dịch trong CSDL mờ được định nghĩa như sau:
6 (1) Quan hệ giao dịch: Hai giao dịch 𝑇1 , 𝑇2 được gọi là có quan hệ với nhau nếu 𝑇1 hoặc là tập con của 𝑇2 hoặc 𝑇1 là tập cha của 𝑇2 . (2) Quan hệ khoảng cách giao dịch: Khoảng cách giữa hai giao dịch là số các mục (item) khác nhau. Trong bảng Bảng 2.2 khoảng cách giữa giao dịch 𝑇1 và 𝑇2 là 𝐷𝑇1−𝑇2 = 2, khoảng cách giữa hai giao dịch 𝑇2 và 𝑇3 Bảng 2.3: Bảng định lượng của cơ sở dữ liệu là 𝐷𝑇1−𝑇3 = 4. Bảng 2.2 2.2.3. Xây dựng bảng định lượng Để giảm số lượng tập ứng cử được tạo ra, cần phải có thêm thông tin để loại bớt các tập không phải là tập phổ biến. Bảng định lượng được xây dựng để lưu các thông tin này khi mỗi giao dịch được xử lý. Các mục xuất hiện trong giao dịch cần sắp xếp theo thứ tự từ điển. Bắt đầu từ các mục bên trái và gọi đó là tiền tố của mục. Sau đó tính chiều dài của giao dịch đầu vào là n, ghi số lượng các mục xuất hiện trong giao dịch vào các mục tùy theo độ dài của giao dịch: L𝑛 , Ln−1 , . . . , L1 . Bảng định lượng bao gồm những mục trong đó mỗi Li chứa một tiền tố mục và giá trị hỗ trợ của mục đó. Bảng 2.3 là bảng định lượng được xây dựng từ CSDL trong Bảng 2.2. Với bảng định lượng, chúng ta có thể dễ dàng loại bớt các tập ứng cử viên có độ hỗ trợ nhỏ hơn so với sự hỗ trợ tối thiểu. 2.3. Nén cơ sở dữ liệu giao dịch Với d là khoảng cách quan hệ được khởi tạo bằng 1. Dựa vào khoảng cách giữa các giao dịch, chúng ta gộp các giao dịch có khoảng cách nhỏ hơn hoặc bằng d để tạo thành nhóm giao dịch mới và đưa vào khối gồm các giao dịch được trộn với nhau. Trong Hình 2.2: CSDL gồm các thuộc tính định lượng, phần Tiền xử lý dữ liệu: Thực hiện chuẩn hoá dữ liệu về đoạn [0,1], độ thuộc của giá trị của các thuộc tính được tính toán như trình trình bày trong mục 2.2, sau đó từ CSDL mờ thu được chúng ta gộp các giao dịch gần nhau vào với nhau tạo ra CSDL mới gọi là CSDL nén. Chi tiết thuật toán nén được trình bày chi tiết trong Thuật toán 1. Để tìm ra các luật kết hợp từ CSDL nén luận án đề xuất cải tiến thuật toán Apriori mờ và chi tiết như Thuật toán 2. Thuật toán 1: Thuật toán nén giao dịch Đầu vào: Cơ sở dữ liệu giao dịch mờ D Đầu ra: Cơ sở dữ liệu nén Ký hiệu các tham số của thuật toán như sau: 𝑀𝐿 = {𝑀𝐿𝑘 }: 𝑀𝐿𝑘 các nhóm giao dịch có độ dài bằng k (độ dài của giao dịch là số mục trong giao dịch) 𝐿 = {𝐿𝑘 }: 𝐿𝑘 các giao dịch có độ dài k 𝑇𝑖 : Giao dịch thứ i trong CSDL mờ | 𝑇𝑖 |: Độ dài của giao dịch 𝑇𝑖 Nội dung thuật toán: Bước 1: Mỗi lần đọc một giao dịch 𝑇𝑖 từ CSDL mờ Bước 2: Tính độ dài của giao dịch 𝑇𝑖 : n Bước 3: Dựa vào giao dịch đầu vào để xây dựng bảng định lượng.
7 Bước 4: Tính toán khoảng cách giữa giao dịch Ti với các nhóm giao dịch trong khối MLn−1 , MLn , MLn+1 . Nếu tồn tại một nhóm giao dịch trong các khối MLn−1 , MLn , MLn+1 có khoảng cách với giao dịch Ti nhỏ hơn hoặc bằng d. Chúng ta tiến hành gộp giao dịch Ti với nhóm giao dịch trong khối tương ứng, ta thu được nhóm giao dịch mới và đưa vào khối có độ dài tương ứng, và xóa nhóm giao dịch cũ trong khối. Bước 5: Nếu giao dịch 𝑇𝑖 không được Hình 2.2: Tổng quan về thuật toán nén gộp với các nhóm giao dịch trong khối CSDL giao dịch MLn−1 , MLn , MLn+1 . Tính toán khoảng cách giữa giao dịch 𝑇𝑖 và các giao dịch trong khối 𝐿𝑛−1 , 𝐿𝑛 , 𝐿𝑛+1 . Nếu tồn tại giao dịch 𝑇𝑗 sao cho 𝐷𝑇𝑖−𝑇𝑗 ≤ 𝑑, gộp giao dịch 𝑇𝑖 với giao dịch 𝑇𝑗 để tạo thành nhóm giao dịch và thêm nhóm giao dịch này vào khối tương ứng (tùy thuộc vào độ dài của nhóm giao dịch được tạo ra), và xóa giao dịch 𝑇𝑗 trong khối: 𝐿𝑛−1 , 𝐿𝑛 , 𝐿𝑛+1 . Nếu không tìm được giao dịch thỏa mãn khoảng cách d, thêm giao dịch 𝑇𝑖 vào khối 𝐿𝑛 . Bước 6: Lặp lại 5 bước trên cho đến khi giao dịch cuối cùng trong CSDL giao dịch được xử lý. Bước 7: Mỗi lần đọc một giao dịch 𝑇𝑖 trong khối 𝐿 = {𝐿𝑘 } Bước 8: Tính độ dài của giao dịch 𝑇𝑖 : n Bước 9: Tính toán khoảng cách giữa giao dịch 𝑇𝑖 với các nhóm giao dịch trong các khối MLn−1 , MLn , MLn+1 . Nếu tồn tại một nhóm giao dịch có khoảng cách nhỏ hơn hoặc bằng d, tiến hành gộp giao dịch 𝑇𝑖 với nhóm giao dịch tìm được để tạo thành nhóm giao dịch mới. Tùy thuộc vào độ dài của nhóm giao dịch mới, sẽ thêm nhóm giao dịch mới này vào khối tương ứng: MLn−1 , MLn , MLn+1 , xóa nhóm giao dịch cũ trong khối: MLn−1 , MLn , MLn+1 , và xóa giao dịch 𝑇𝑖 trong khối 𝐿𝑛 . Bước 10: Lặp lại bước 7, bước 8, bước 9 cho đến khi giao dịch cuối cùng trong 𝐿 = {𝐿𝑘 } được xử lý. Kết quả thu được CSDL nén gồm các giao dịch trong các khối 𝐿 = {𝐿𝑘 }, 𝑀𝐿 = {𝑀𝐿𝑘 }, và bảng định lượng. 2.4. Thuật toán trích xuất luật kết hợp mờ Thuật toán 2: Khai phá dữ liệu mờ theo hướng tiếp cận ĐSGT. Ký hiệu các tham số của thuật toán khai phá luật kết hợp mờ theo hướng tiếp cận ĐSGT: N: Tổng số giao dịch trong CSDL M: Tổng số thuộc tính 𝐴𝑗 : Thuộc tính thứ j, 1 ≤ 𝑗 ≤ 𝑚 (thuộc tính định lượng hoặc thuộc tính hạng mục) |𝐴𝑗 |: Số nhãn gia tử của thuộc tính Aj 𝑅𝑗𝑘 : Nhãn gia tử j của thuộc tính Aj , 1 ≤ 𝑘 ≤ |Aj | 𝐷 (𝑖) : Dữ liệu giao dịch thứ i, 1 ≤ 𝑖 ≤ 𝑁 (𝑘) 𝑣𝑗 : Giá trị phần tử thứ k của Aj trong D(i)
8 (𝑖) (k) (𝑖) 𝑓𝑗𝑘 : Giá trị độ thuộc của 𝑣j với nhãn gia tử R jk , 0 ≤ 𝑓𝑗𝑘 ≤ 1 𝑆𝑢𝑝(𝑅𝑗𝑘 ): Độ hỗ trợ của R jk 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 R jk 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ợ CSDL nén, Sử dụng 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 < 𝐴: start1 . . end1 >, < 𝐴: start 2 . . end2 >, …, < 𝐴: start q . . endq >. Giá trị của một bản ghi tại trường < 𝐴: start i . . endi > 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 [start i . . 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 ) 𝐵 𝐸𝐺 𝐸 𝜈(𝑥3 ) 𝐸𝐹 𝜈(𝑥2 )𝐸 nên )𝐵 = )𝜈(𝑥 ) . Tương tự )𝐶 = )𝜈(𝑥 ) . Ngoài ra, 𝜈(𝑥2 ) 𝐵 = 𝜈(𝑥3 ) 𝐶 = 1 𝜈(𝑥2 𝜈(𝑥2 3 𝑣(𝑥3 𝜈(𝑥2 3 𝐸𝐹 𝐸 𝜈(𝑥2 ) nên cuối cùng ta có = ) . Từ đó dễ dàng suy ra thực chất hai cách gắn độ thuộc này 𝐸𝐺 𝐸 𝜈(𝑥3 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 Hình 3.2: Phân hoạch miền giá trị luật kết hợp mà ta khai phá được chỉ bao gồm của thuộc tính dựa trên biểu diễn đơn các hạng từ có cùng độ dài, mà điều đó làm thể hạt 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
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 Hình 3.4: Phân hoạch miền giá trị của thuộc vì nằm trong bản thân cách xây tính dựa trên biểu diễn đa thể hạt dựng ĐSGT. Trong lý thuyế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 như trình bày trong mục 3.2 để tính toán hàm mục tiêu. Kết thúc bước 1 chúng ta thu được tập các tham số của các ĐSGT. Từ các tham số của các ĐSGT, chúng ta có thể dễ dàng xây dựng các hàm thuộc ở bước 2. Bước 2: Khai phá luật kết hợp: Chúng ta sử dụng các tham số ĐSGT thu được ở bước 1 để mờ hoá CSDL giao dịch và tiến hành khai phá luật kết hợp mờ. Kết thúc bước này chúng ta thu được tập các luật kết hợp biểu thị bằng thông tin ngôn ngữ. 3.3.1. Mã hóa tập các MF Để xây dựng các hàm thuộc cho các thuộc tính, trong luận án sử dụng ĐSGT có cấu trúc 𝐴𝑋 = (𝑋, 𝐺, 𝐻, ≤) trong đó: 𝐺 = {𝐶 − = {𝐿𝑜𝑤} ∪ 𝐶 + = {𝐻𝑖𝑔ℎ}}; 𝐻 = {𝐻 − = {𝐿𝑖𝑡𝑡𝑙𝑒} ∪
17 𝐻 + = {𝑉𝑒𝑟𝑦}}; 𝛼 = 𝜇(𝐿𝑖𝑡𝑡𝑙𝑒) = 1 − 𝜇(𝑉𝑒𝑟𝑦), 𝛽 = 𝜇(𝑉𝑒𝑟𝑦); 𝑤 = 𝑓𝑚(𝐿𝑜𝑤) = 1 − 𝑓𝑚(𝐻𝑖𝑔ℎ). Với cấu trúc ĐSGT trên gồm bộ bốn tham số: 𝜇(𝐿𝑖𝑡𝑡𝑙𝑒), 𝜇(𝑉𝑒𝑟𝑦), 𝑓𝑚(𝐶 − ), 𝑓𝑚(𝐶 + ). Tham số 𝛼 = 𝜇(𝑉𝑒𝑟𝑦) = 1 − 𝜇(𝐿𝑖𝑡𝑡𝑙𝑒), và 𝑤 = 𝑓𝑚(𝐿𝑜𝑤) = 1 − 𝑓𝑚(𝐻𝑖𝑔ℎ), vì vậy với mỗi ĐSGT chúng ta chỉ cần tìm hai tham số 𝛼 và 𝑤 thay vì tìm cả bốn tham số. Dựa vào các tham số của ĐSGT của các thuộc tính, chúng ta xây dựng các hàm thuộc theo dạng đơn thể hạt như trình bày mục 3.2.1 hoặc biểu diễn đa thể hạt như trình bà ytrong mục 3.2.2. Chúng ta cần phải cần phải tìm kiếm các tham số mờ của các ĐSGT 𝐴𝑋𝑖 cho n thuộc tính định lượng, mỗi ĐSGT gồm có hai tham số 𝛼𝑖 , 𝑤𝑖 (i=1,…,n). Như vậy để biểu diễn một nhiệm sắc thể cần một mảng số thực có kích thước 2*n. Cấu trúc một gene như sau: (𝛼 , … , 𝛼 , 𝑤 , … , 𝑤 ) (3.1) 1 𝑛 1 𝑛 3.3.2. Đánh giá nhiễm sắc thể Hàm mục tiêu của một nhiễm sắc thể 𝐶𝑞 được định nghĩa như sau: ∑𝑥∈𝐿1 𝑓𝑢𝑧𝑧y_support(x) (3.2) 𝑓𝑖𝑡𝑛𝑒𝑠𝑠(𝐶𝑞 ) = 𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞 ) Với: 𝐿1 là tập phổ biến 1-Itemset sử dụng tập các hàm MF trong 𝐶𝑞 . Với 𝑓𝑢𝑧𝑧𝑦_𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝑥) độ hỗ trợ mờ của 1-Itemset x được tính toán từ CSDL giao dịch, 𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞 ) mức độ phù hợp phù hợp của MF trong 𝐶𝑞 . Mức độ phù hợp của tập các MF trong nhiệm sắc thể 𝐶𝑞 được định nghĩa như sau: 𝑛 𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞 ) = ∑[𝑜𝑣𝑒𝑟𝑙𝑎𝑝_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘 ) + 𝑐𝑜𝑣𝑒𝑟𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘 )] (3.3) 𝑘=1 Với n là số lượng item, 𝑜𝑣𝑒𝑟𝑙𝑎𝑝_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘 ) là mức độ chồng lên nhau của các MF của item 𝐼𝑘 trong nhiệm sắc thể 𝐶𝑞 , và 𝑐𝑜𝑣𝑒𝑟𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘 ) là mức độ bao phủ của các MF đối với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 . 𝑂𝑣𝑒𝑟𝑙𝑎𝑝_𝑓𝑎𝑐𝑡𝑜𝑟 biểu diễn tỷ lệ các MF chồng lên nhau của item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 . Overlap factor của MF đối với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 được định nghĩa như sau: 𝑜𝑣𝑒𝑟𝑙𝑎𝑝(𝑅𝑖 ,𝑅𝑗 ) (3.4) Overlap_factor(𝐶𝑞𝑘 ) = ∑𝑚 𝑚 𝑘=1 ∑𝑗=𝑖+1 [𝑚𝑎𝑥 ( , 1) − 1] 𝑚𝑖𝑛(𝑠𝑝𝑎𝑛𝑅𝑅 ,𝑠𝑝𝑎𝑛𝐿𝑅 ,) 𝑖 𝑗 𝐶𝑜𝑣𝑒𝑟𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟 biểu diễn tỷ lệ bao phủ của các MF đối với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 . Coverage_factor của MF đối với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 được định nghĩa: 1 Coverage_factor(𝐶𝑞𝑘 ) = (3.5) 𝑅𝑎𝑛𝑔(𝑅1 , … , 𝑅𝑚 ) 𝑚𝑎𝑥(𝐼𝑘 ) Với 𝑅𝑎𝑛𝑔(𝑅1 , … , 𝑅𝑚 ) là phạm vi bao phủ của MF và 𝑚𝑎𝑥(𝐼𝑘 ) giá trị lớn nhất của 𝐼𝑘 trong giao dịch. 3.4. Thuật toán tìm kiếm phân hoạch mờ tối ưu và luật kết hợp Thuật toán gồm hai pha: Pha 1: Tìm kiếm phân hoạch mờ tối ưu dựa vào CSDL giao dịch đầu vào.