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 (Tóm tắt)

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.

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:

(𝑥) = 0

(𝑥) liên tục; (𝑥) đơn điệu tăng trên [𝑝𝑘−1, 𝑝𝑘]; (𝑥) > 0;

𝑚 𝑘=1

; (𝑥) = 1 𝜇𝐴𝑘

(𝑥) là hàm đối xứng (𝒙) có cùng một dạng hình họcĐại số gia tử

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à (𝑝𝑘) (𝑝𝑘 thuộc một phân hoạch mờ của 𝑈 nếu các điều kiện sau thoả mãn, ∀𝑘 = 1, … , 𝑚:𝜇𝐴𝑘 về phần được gọi là lõi của 𝐴𝑘); 2) Nếu x ∉ [𝑝𝑘−1, 𝑝𝑘+1] thì 𝜇𝐴𝑘 3) 𝜇𝐴𝑘 4) 𝜇𝐴𝑘 5) ∀𝑥 ∈ 𝑈, ∃𝑘, sao cho 𝜇𝐴𝑘 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) ∀𝑥𝜖𝑈, ∑ 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ờ 𝜇𝐴𝑘 1.2. Các tập mờ 𝝁𝑨𝒌 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) 𝑣𝔵(𝑊) =  = 𝑓𝑚(𝑐−), 𝑣𝔵(𝑐−) =  – . 𝑓𝑚(𝑐−) = . 𝑓𝑚(𝑐−), 𝑣(𝑐+) =  + . 𝑓𝑚(𝑐+);

𝑖−𝑠𝑖𝑔𝑛(𝑗) 𝑖=𝑠𝑖𝑔𝑛(𝑗)

}, (2) 𝑣𝔵(ℎ𝑗𝑥) = 𝑣𝔵(𝑥) + 𝑆𝑖𝑔𝑛(ℎ𝑗𝑥) {∑ 𝜇(ℎ𝑖)𝑓𝑚(𝑥) − 𝜔(ℎ𝑗𝑥)𝜇(ℎ𝑗)𝑓𝑚(𝑥)

[1 + 𝑆𝑖𝑔𝑛(ℎ𝑗𝑥) 𝑆𝑖𝑔𝑛(ℎ𝑝ℎ𝑗𝑥) (𝛽 −

với mọi j, −𝑞 ≤ 𝑗 ≤ 𝑝 và 𝑗  0, trong đó 𝜔(ℎ𝑗𝑥) = 𝛼)] ∈ {𝛼, 𝛽}; 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ờ

𝑛 𝑖=1

𝑚 𝑗=1

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.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: 𝑓𝑠(〈𝑍, 𝐶〉) ≥ 𝑓𝑚𝑖𝑛𝑠𝑢𝑝

fc → Z\Z′is C\C′.

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 tính mờ phổ biến thì luật kết hợp được sinh ra từ X có dạng: Z′is 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

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ờ.

xi nhất về hai phía có thể dùng để xác định độ gần gũi của dj

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 đó, xi của 𝑥𝑖 đều nằm giữa 2 giá trị định lượng ngữ nghĩa nào đó của 2 phần xi và giá trị định lượng ngữ nghĩa của hai xi vào hai miền

xi của thuộc tính 𝑥𝑖 vào miền mờ 𝑠𝑗: xi |, với 𝑣(𝑠𝑗) là giá trị định lượng ngữ nghĩa của phần tử 𝑠𝑗.

Hình 2.1: Xây dựng phân hoạch mờ dựa trên ĐSGT một giá trị bất kỳ dj tử của 𝐴𝑋𝑖. Khoảng cách trên đoạn [0,1] giữa dj phần tử gần dj mờ (hai phần tử của ĐSGT). Độ xi với các phần tử gần gũi giữa dj 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ị xi một cặp độ thuộc. dj

B 40 48 32

TID 𝑇1 𝑇2 𝑇3

TID

B4 0 0 0

A4 0 0 0

A2 0.925 0.965 0.925

A1 0.825 0 0

A3 0 0.785 0.825

B1 0 0 0.805

B2 0.975 0.895 0.945

B3 0.775 0.855 0

Chúng ta có các giá trị được mờ hóa như trong Bảng 2.2. Ký hiệu: A1, B1: Very Low; A2, B2: Least Low; A3, B3: Least Heigh, A4, B4: Very Heigh; Như vậy để tính độ thuộc dj xi) = 1 − | 𝑣(𝑠𝑗) − dj 𝜇𝑠𝑗 (dj Bảng 2.1: Cơ sở dữ liệu ví dụ A 30 41 45 Bảng 2.2: Mờ hóa dữ liệu trong Bảng 2.1

𝑇1 𝑇2 𝑇3 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.

được định nghĩa như sau:

Quan hệ giao dịch và quan hệ khoảng cách giao dịch cho các giao dịch trong CSDL mờ

(1) Quan hệ giao dịch: Hai giao dịch 𝑇1, 𝑇2 được gọi là có quan hệ với nhau nếu 𝑇1hoặc là tập con của 𝑇2 hoặc 𝑇1là 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.

Bảng 2.3: Bảng định lượng của cơ sở dữ liệu Bảng 2.2

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 là 𝐷𝑇1−𝑇3 = 4. 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.

Hình 2.2: Tổng quan về thuật toán nén CSDL giao dịch

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 gộp với các nhóm giao dịch trong khối 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) 𝑣𝑗

(𝑖) ≤ 1

(k) với nhãn gia tử Rjk, 0 ≤ 𝑓𝑗𝑘

(𝑖): Giá trị độ thuộc của 𝑣j 𝑓𝑗𝑘 𝑆𝑢𝑝(𝑅𝑗𝑘): Độ 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 𝑀𝑖𝑛_𝑐𝑜𝑛𝑓.

(𝑘)

(𝑘), 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ì 𝑣𝑗

(𝑘)

(𝑘) của giao dịch 𝐴𝑗 trong 𝐷(𝑖), với i từ 1 tới N. (𝑘) được biểu diễn bởi 2 nhãn gia tử (𝑘), mỗi nhãn ứng với 1 giá trị biểu với nhãn gia tử đó. Độ thuộc này được tính là khoảng

(𝑖)(j = 1, 2) của 𝑣𝑗

(𝑘) tới giá trị biểu diễn cho nhãn gia tử tương ứng.

Output: Luật kết hợp mờ Bước 1: Chuyển các giá trị định lượng 𝑣𝑗

Với 𝑣𝑗 chỉ có 1 nhãn gia tử ứng với đầu mút đó. Ngược lại 𝑣𝑗 liên tiếp có đoạn giá trị nhỏ nhất trên trường giá trị của 𝑣𝑗 diễn độ thuộc 𝑓𝑗𝑘 cách của 𝑣𝑗 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.

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

Sử dụng nén

CSDL nén

Độ hỗ trợ (%) 20 30 40 50 60 70

238 98 34 18 6 2

CSDL nén, và Bảng định lượng 255 94 34 18 6 2

255 94 34 18 6 2

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%

STT

Luật kết hợp

Đỗ hỗ trợ

Độ tin cậy

CSDL không nén

{ VL_INCHEAD } ==> { VL_INCFAM } { VL_INCFAM } ==> { VL_INCHEAD } { LY_AGE } ==> { VL_INCHEAD } { LY_AGE } ==> { VL_INCFAM } { VL_INCHEAD, LY_AGE } ==> { VL_INCFAM } { VL_INCFAM, LY_AGE } ==> { VL_INCHEAD }

1 2 3 4 5 6

92% 92% 69% 70% 69% 69%

97% 98% 98% 99% 99% 99%

CSDL giao dịch nén, không sử dụng bảng định lượng

1 2 3 4 5 6

91% 91% 69% 69% 69% 69%

98% 99% 99% 100% 100% 99%

CSDL giao dịch nén, và sử dụng bảng định lượng

{ VL_INCHEAD } ==> { VL_INCFAM } { VL_INCFAM } ==> { VL_INCHEAD } { LY_AGE } ==> { VL_INCHEAD } { LY_AGE } ==> { VL_INCFAM } { LY_AGE, VL_INCHEAD } ==> { VL_INCFAM } { LY_AGE, VL_INCFAM } ==> { VL_INCHEAD }

1 2 3 4 5 6

91% 91% 69% 69% 69% 69%

98% 99% 99% 100% 100% 99%

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%

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 2

{ VL_INCHEAD } ==> { VL_INCFAM } { VL_INCFAM } ==> { VL_INCHEAD }

97% 98%

1 2

{ VL_INCHEAD } ==> { VL_INCFAM } { VL_INCFAM } ==> { VL_INCHEAD }

98% 99%

1 2

{ VL_INCHEAD } ==> { VL_INCFAM } { VL_INCFAM } ==> { VL_INCHEAD }

98% 99%

92% 92% CSDL giao dịch nén, không sử dụng bảng định lượng 91% 91% CSDL giao dịch nén, và sử dụng bảng định lượng 91% 91% Hình 2.3: Thời gian thực hiện với CSDL nén

Độ hỗ trợ (%) 5% 10% 20% 30% 40% 50% 60% 70% 80%

CSDL nén, và Bảng định lượng 8185 5527 2528 1318 599 287 155 75 35

CSDL không nén 7822 5076 2149 1096 587 248 107 75 23

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.

Độ hỗ trợ (%) 5% 10% 20% 30% 40% 50%

CSDL không nén 669 580 187 72 26 8

CSDL nén, và Bảng định lượng 41.4 26.3 8.3 3.5 1.1 0.4

CSDL nén 41.4 26.4 8.3 3.6 1.1 0.4

Bảng 2.7: Số lượng luật kết hợp thu được với độ tin cậy 80% CSDL nén 8188 5532 2528 1348 599 287 155 75 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%

3 1

60% 70%

0.2 0.1

0.2 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

Độ tin cậy

Đỗ hỗ trợ

CSDL không nén

1 2 3 4 5 6 7 8 9

{ LL_A5 } ==> { LH_A2 } { LH_A2 } ==> { LL_A5 } { LL_A5 } ==> { VH_A1 } { VH_A1 } ==> { LL_A5 } { LH_A2 } ==> { VH_A1 } { VH_A1 } ==> { LH_A2 } { LL_A5, VH_A1 } ==> { LH_A2 } { LH_A2, VH_A1 } ==> { LL_A5 } { LH_A2, LL_A5 } ==> { VH_A1 }

86 % 86 % 88 % 88 % 92 % 92 % 85 % 85 % 85 %

97 % 93 % 99 % 91 % 99 % 95 % 97 % 93 % 100 %

CSDL giao dịch nén, không Bảng định lượng

1 2 3 4 5 6 7 8 9

88 % 88 % 88 % 88 % 92 % 92 % 87 % 87 % 87 %

99 % 95 % 100 % 91 % 100 % 95 % 99 % 95 % 100 %

CSDL giao dịch nén, và Bảng định lượng

1 2 3 4 5 6 7 8 9

{ B3 } ==> { A4 } { A4 } ==> { B3 } { E2 } ==> { A4 } { A4 } ==> { E2 } { E2 } ==> { B3 } { B3 } ==> { E2 } { B3, E2 } ==> { A4 } { A4, E2 } ==> { B3 } { A4, B3 } ==> { E2 }

92 % 92 % 88 % 88 % 88 % 88 % 87 % 87 % 87 %

100 % 95 % 100 % 91 % 99 % 95 % 100 % 99 % 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

Độ tin cậy

Đỗ hỗ trợ

CSDL không nén

1 2

92 % 92 %

99 % 95 %

{ LH_A2 } ==> { VH_A1 } { VH_A1 } ==> { LH_A2 }

CSDL giao dịch nén, không Bảng định lượng

1 2

92 % 92 %

100 % 95 %

{ LH_A2 } ==> { VH_A1 } { VH_A1 } ==> { LH_A2 }

CSDL giao dịch nén, và Bảng định lượng

{ B3 } ==> { A4 } { A4 } ==> { B3 }

92 % 92 %

100 % 95 %

1 2 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.

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 >, < 𝐴: start2. . end2 >, …, < 𝐴: startq. . endq >. Giá trị của một bản ghi tại trường < 𝐴: starti. . 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 [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

đị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

𝐸𝐹 𝑣(𝑥3)𝐶

𝜈(𝑥2)𝐸 𝜈(𝑥2)𝜈(𝑥3)

𝐸𝐺 𝜈(𝑥2)𝐵

𝐸 𝜈(𝑥3) 𝜈(𝑥2)𝜈(𝑥3) 𝐸𝐹

. Tương tự = = 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) 𝐵 . Ngoài ra, 𝜈(𝑥2) 𝐵 = 𝜈(𝑥3) 𝐶 = 1 nên

𝐸𝐺

𝐸 𝜈(𝑥2) 𝐸 𝜈(𝑥3)

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 =

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

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

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

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ớ.

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 lý

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 thuyết dựng ĐSGT. Trong

Đ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 đó: 𝐺 = {𝐶− = {𝐿𝑜𝑤} ∪ 𝐶+ = {𝐻𝑖𝑔ℎ}}; 𝐻 = {𝐻− = {𝐿𝑖𝑡𝑡𝑙𝑒} ∪

𝐻+ = {𝑉𝑒𝑟𝑦}}; 𝛼 = 𝜇(𝐿𝑖𝑡𝑡𝑙𝑒) = 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.

(3.1) 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: (𝛼1, … , 𝛼𝑛, 𝑤1, … , 𝑤𝑛) 3.3.2. Đánh giá nhiễm sắc thể

𝑥∈𝐿1

∑ Hàm mục tiêu của một nhiễm sắc thể 𝐶𝑞 được định nghĩa như sau: 𝑓𝑢𝑧𝑧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:

𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞) = ∑[𝑜𝑣𝑒𝑟𝑙𝑎𝑝_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘) + 𝑐𝑜𝑣𝑒𝑟𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟(𝐶𝑞𝑘)]

𝑘=1

(3.3)

𝑜𝑣𝑒𝑟𝑙𝑎𝑝(𝑅𝑖,𝑅𝑗)

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ể 𝐶𝑞.

𝑚 𝑘=1

𝑚 𝑗=𝑖+1

𝑚𝑖𝑛(𝑠𝑝𝑎𝑛𝑅𝑅𝑖

,𝑠𝑝𝑎𝑛𝐿𝑅𝑗

Overlap factor của MF đối với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 được định nghĩa như sau: (3.4) ∑ [𝑚𝑎𝑥 ( , 1) − 1] Overlap_factor(𝐶𝑞𝑘) = ∑

𝐶𝑜𝑣𝑒𝑟𝑎𝑔𝑒_𝑓𝑎𝑐𝑡𝑜𝑟 biểu diễn tỷ lệ bao phủ của các MF đối với item 𝐼𝑘 trong nhiễm sắc

Coverage_factor(𝐶𝑞𝑘) = (3.5)

thể 𝐶𝑞. Coverage_factor của MF đối với item 𝐼𝑘 trong nhiễm sắc thể 𝐶𝑞 được định nghĩa: 1 𝑅𝑎𝑛𝑔(𝑅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.

Pha 2: Sử dụng thuật toán khai phá luật kết hợp mờ với các MF có được trong Pha 1. Nội dung thuật toán: Đầu vào: T giao dịch số, tập gồm n mục (thuộc tính), mỗi mục gồm m hạng từ ngôn ngữ, độ hỗ trợ min_𝑠𝑢𝑝𝑝, và độ tin cậy min_𝑐𝑜𝑛𝑓 và kích thước quần thể N.

Đầu ra: Tập các luật kết hợp mờ và tập hàm thuộc MF. Nội dung thuật toán: Pha 1: Tìm kiếm phân hoạch mờ tối ưu từ CSDL giao dịch T Bước 1: Khởi tạo quần thể gồm N nhiễm sắc thể ngẫu nhiên. Nhiễm sắc thể biểu diễn có dạng (𝛼1, … , 𝛼𝑛, 𝑤1, … , 𝑤𝑛). Với mỗi cặp (𝛼𝑖, 𝑤𝑖) là một ĐSGT, với i=1,..,n.

Bước 2: Mã hóa các hàm thuộc thành chuỗi mã hóa như trình bày ở mục 3.3.1. Dựa vào các ĐSGT có được trong Bước 1, xây dựng các hàm thuộc cho các thuộc tính trong CSDL gốc như trình bày trong phần 3.2. Chúng ta có thể sử dụng biểu diễn hàm thuộc dạng Đơn thể hạt hoặc Đa thể hạt.

(𝑖) như sau: (

Bước 3: Tính toán hàm mục tiêu cho mỗi nhiễm sắc thể trong quần thể như sau: Bước 3.1: Mỗi giao dịch và 𝐷𝑖, với i=1…n, mỗi thuộc tính 𝐼𝑗, j=1…m biến đổi thành giá

(𝑖) 𝑓𝑗1 𝑅𝑗1

(𝑖) 𝑓𝑗2 𝑅𝑗2

(𝑖) 𝑓𝑗𝑙 𝑅𝑗𝑙

+ + ⋯ + ) để biểu diễn tập hàm thuộc của một nhiễm sắc trị số 𝑣𝑗

(𝑖) là giá trị của hàm thuộc thứ j của item 𝐼𝑗,

thể.

(𝑖): 𝑣𝑗

(𝑖)

Với 𝑅𝑗𝑘 là vùng mờ thứ k của item 𝐼𝑗, 𝑓𝑗𝑙 l là số miền mờ. Bước 3.2: Tính toán giá trị mỗi miền mờ:

𝑛 𝑖=1

(3.6) 𝑐𝑜𝑢𝑛𝑡𝑗𝑘 = ∑ 𝑓𝑗

Bước 3.3: Mỗi miền mờ 𝑅𝑗𝑘, 1 ≤ 𝑗 ≤ 𝑚, 1 ≤ 𝑘 ≤ |𝐼𝑗|, kiểm tra giá trị 𝑐𝑜𝑢𝑛𝑡𝑗𝑘 so với ngưỡng độ hỗ trợ tối thiểu min_supp. Nếu 𝑅𝑗𝑘 thỏa mãn điều kiện thì đưa vào tập phổ biến 1-Itemset (𝐿1). 𝐿1 = {𝑅𝑗𝑘| 𝑐𝑜𝑢𝑛𝑡𝑗𝑘 ≥ 𝛼, 1 ≤ 𝑗 ≤ 𝑚, 1 ≤ 𝑘 ≤ |𝐼𝑗|}

𝑥∈𝐿1

∑ Bước 3.4: Giá trị mục tiêu của nhiễm sắc thể được tính theo công thức sau: 𝑓𝑢𝑧𝑧𝑦_𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝑥) (3.7) 𝑓𝑖𝑡𝑛𝑒𝑠𝑠(𝐶𝑞) = 𝑠𝑢𝑖𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝐶𝑞)

Bước 4: Thực hiện phép lai tạo trong quần thể. Bước 5: Sử dụng phép chọn lọc theo điều kiện để chọn các cá thể trong quần thể để tạo thế hệ tiếp theo. Bước 6: Nếu điều kiện dừng chưa thỏa mãn thì quay lại Bước 3, ngược lại thực hiện bước tiếp theo. Bước 7: Hàm thuộc được lựa chọn từ cá thể có giá trị hàm mục tiêu lớn nhất trong quần thể.

Pha 2: Khai phá luật kết hợp mờ Sử dụng thuật toán khai phá luật kết hợp mờ. 3.5. Kết quả thực nghiệm

Trong phần này sẽ mô tả CSDL dùng trong thử nghiệm và các kết quả thử nghiệm với hai phương pháp luận án đề xuất: sử dụng biểu diễn dữ liệu dạng đơn thể hạt và sử dụng biểu diễn dữ liệu dạng đa thể hạt.

Các tham số của giải thuật GA như sau: kích thước quần thể 50; số thế hệ 10000, số bít

cho mỗi gen là 30, xác suất lai tạo 0.6. 3.5.1. Cơ sở dữ liệu sử dụng trong thử nghiệm CSDL được sử dụng trong thử nghiệm gồm: FAM95, pollution, stulong, basketball,

quake, stock. . 3.5.2. Phân tích và đánh giá kết quả thực nghiệm với biểu diễn dữ liệu dạng đơn thể hạt Trong phần này các kết quả thu được từ thử nghiệm với biểu diễn hàm thuộc dang đơn thể hạt. Mỗi mục (thuộc tính) được chia làm 5 miền mờ có các nhãn tương ứng trong ĐSGT là {0, 𝑐−, 𝑊, 𝑐+, 1}. Phương pháp sử dụng ĐSGT được so sánh với 3 phương pháp khác: Phương pháp do Herrera và cộng sự [53], phương pháp của Hong và cộng sự [42] và phương pháp phân chia đều miền giá trị của thuộc tính bằng các MF đồng dạng. 3.5.2.1. Kết quả thử nghiệm với CSDL FAM95

A10

𝜇(𝐿) 𝜇(𝑉) 𝑓𝑚(𝐶−) 𝑓𝑚(𝐶+)

0.679 0.350 0.610 0.649 0.214 0.379 0.202 0.704 0.231 0.213 0.321 0.650 0.390 0.351 0.786 0.621 0.798 0.296 0.769 0.787 0.504 0.764 0.799 0.756 0.732 0.479 0.800 0.499 0.765 0.776 0.496 0.236 0.201 0.244 0.268 0.521 0.200 0.501 0.235 0.224 Kết quả thu được như trong Bảng 3.6, với 𝐹𝑠𝑢𝑝: Tổng độ hỗ trợ của các tập phổ biến 1- ItemSet, Fit: Giá trị hàm mục tiêu, Suit: Độ phù hợp, #1I: Số lượng 1-ItemSet, Interest: độ thú vị trung bình của các luật.

Trong Bảng 3.5 là các tham số mờ của các ĐSGT của 10 thuộc tính số thu được sau khi chạy giải thuật di truyền. Các tham số này được sử dụng để xây dựng các hàm thuộc theo dạng biểu diễn đơn thể hạt như đã trình bày trong mục 3.2.1. Bảng 3.5: Các tham số mờ của các ĐSGT được tối ưu của 10 thuộc tính với phương pháp sử dụng biểu diễn đơn thể hạt A3

Từ kết quả trên có thể thấy: - So với phương pháp phương pháp do Herrera và cộng sự [53], phương pháp của Hong và cộng sự [42] là như nhau.

Fsup 9.83 7.87 6.62 0.94

Suit 10 10 10 10

Min Sup (%) 20 50 70 90

#1I 22 10 8 1

- Phương pháp phân chia đều kém hơn phương pháp sử dụng ĐSGT Với độ hỗ trợ min_supp = 50%, phương pháp ĐSGT có kém chút ít phương pháp của nhóm Herrera và nhóm Hong về số tập phố biến 1-ItemSet. Với độ hỗ trợ min_supp = 70% phương pháp sử dụng ĐSGT kém hơn phương pháp do Herrera đề xuất, nhưng hơn hai phương pháp còn lại..

Fsup 10.46 9.92 7.69

Suit 10.99 12.92 12.57

Min Sup (%) 20 50 70

#1I 22 15 10

Bảng 3.6: Kết quả thử nghiệm biểu diễn đơn thể hạt Phương pháp đề xuất sử dụng ĐSGT Fit 0.98 0.79 0.66 0.09 Phương pháp của Herrera và cộng sự Fit 0.95 0.77 0.61

0.10

0.92

10.0

Phương pháp của Hong và cộng sự Fit 0.53 0.38 0.20 0.06

Fsup 10.22 7.95 3.96 0.90

Suit 19.27 20.63 19.54 15.01

#1I 22 12 5 1

Min Sup (%) 20 50 70 90

Phương pháp phân chia đều

Fit 0.94 0.46 0.24 0.00

Fsup 9.43 4.57 2.36 0.00

Suit 10 10 10 10

#1I 21 7 3 0

Min Sup (%) 20 50 70 90

Với mục tiêu, xây dựng các hàm thuộc sao cho không chồng lên nhau quá nhiều, và không rời rạc nhau. Giá trị Suit (độ phù hợp của các MF) trong hàm mục giúp chúng ta tìm kiếm các hàm thuộc đảm bảo điều này. Trong Bảng 3.6 cho thấy, phương pháp sử dụng ĐSGT có giá trị Suit thấp hơn phương pháp Herrera và Hong. Giá trị Suit nhỏ giúp cho giá trị hàm mục tiêu càng lớn. Điều đó cho thấy, các hàm thuộc được xây dựng bằng phương pháp sử dụng ĐSGT gia tử cho kết quả tốt hơn (Hình 3.9). Kết quả của nhóm Herrera tuy có tốt hơn về mặt số tập phố biến 1-ItemSet (trong Bảng 3.6 giá trị 1-ItemSet lần lượt là 22, 15, 10, 1) nhưng các tập MF thu được sau khi chạy GA thì rất không tốt (xem Hình 3.14: hình vẽ MF với độ hỗ trợ tối thiểu 20% dưới đây để thấy rõ).

Min support (%) PP ĐSGT PP Herrera PP Phân chia đều Bảng 3.7: Quan hệ giữa độ thú vị trung bình của các luật 60 0.771 0.767 0.774 20 0.383 0.368 0.385 30 0.516 0.483 0.489 40 0.585 0.591 0.606 50 0.713 0.669 0.672 70 0.82 0.822 0.821

Trong Hình 3.12 cho thấy số lượng 1-ItemSet của phương pháp ĐSGT kém hơn so với kết quả Herrera và hơn so với các phương pháp còn lại. Tuy nhiên dựa vào giá trị Suit trong Bảng 3.6 và bằng trực quan trong Hình 3.14 cho thấy hàm thuộc của nhóm Herrera có độ chồng lấn quá nhiều, có một số hai hàm thuộc gần như chồng khít lên nhau.

Trong thử nghiệm, độ thú vị của luật được tính theo công thức 2.5 trong mục 1.4.1. Từ kết quả trong Bảng 3.7 cho thấy độ thú vị trung bình của các luật của phương pháp sử dụng ĐSGT cao hơn hoặc bằng hai phương pháp còn lại.

Hình 3.14: Tập hàm thuộc thu được sau khi thực hiện GA với phương pháp của Herrera sử dụng lý thuyết tập mờ

Trong Hình 3.14 có thể thấy, kết quả thu được tập các MF đều có 1 cặp MF gần như chồng khít, không thỏa mãn tiêu chí về độ chồng lấn. Điều này chứng tỏ kết quả phân chia miền mờ của phương pháp này không tốt (ở đây kết quả chỉ ra một điều là có lẽ chia thành 4 miền mờ thì hợp lý hơn, khi đó các nhãn ngôn ngữ cũng sẽ khác, chỉ có 4 thay vì 5). Vấn đề lựa chọn không chỉ các hàm MF phân chia miền xác định của mục khi cố định số lượng (thí dụ như 5) mà hơn nữa, lựa chọn chính số lượng đó cho từng mục là vấn đề đáng được quan tâm vì có thể thấy các chỉ số nêu trên bảng trên phụ thuộc nhiều vào số lượng của các MF cho từng mục.

Trong chương này, luận án trình bày thuật toán tối ưu hóa cả số lượng lẫn thông số các MF cho các thuộc tính định tính nhằm tới kết quả tốt nhất khi khai phá dữ liệu thông qua việc sử dụng khái niệm đa thể hạt khi phân chia miền mờ. Các hình ảnh cho tập MF theo phương pháp ĐSGT được đưa ra trong Hình 3.15. Tất nhiên, các tam giác biểu diễn các MF ở đây vẫn tạo nên một phân hoạch mạnh theo cách ta xây dựng.

Hình 3.15 là tập các hàm thuộc của 10 thuộc tính thu được sau khi thực hiện tối ưu bằng giải thuật di truyền. Bằng trực quan chúng ta có thể thấy, các tập mờ có sự phân bố đều đảm bảo độ chồng lấn giữa các tập mờ vừa phải và các tập mờ phủ toàn bộ trên miền giá trị của thuộc tính.

Hình 3.15: Tập hàm thuộc thu được sau khi thực hiện GA với phương pháp sử dụng biểu diễn đơn thể hạt và ĐSGT 3.5.2.2. Kết quả thử nghiệm với một số CSDL khác

Trong mục này, luận án sử dụng cấu trúc ĐSGT như trọng mục 3.5.2.1, và trình bày kết quả thử nghiệm với 5 CSDL gồm: Pollution, Stulong, Basketball, Quake, Stock. Luận án trình bày so sánh kết quả đề xuất với hai phương pháp khác là: Phương pháp do Herrera và cộng sự [53], phương pháp của Hong và cộng sự [42]. Trong Bảng 3.8 là số lượng tập phổ biến 1-ItemSet, Bảng 3.9 là độ thú vị trung bình. Bảng 3.8: Bảng số lượng tập phổ biến 1-ItemSet

CSDL Min Supp (%)

pollution

stulong

20 50 70 90 20 50 70 90

PP đề xuất PP Herrera PP Hong 45 14 2 0 13 10 5 0

56 43 18 1 17 13 13 2

37 15 5 1 10 5 5 0

CSDL

pollution

stulong

Bảng 3.9: Bảng Độ thú vị trung bình PP đề xuất 0.351 0.643 0.823 0.487 0.754 0.824

PP Herrera 0.349 0.665 0.918 0.457 0.651 0.783

Min Supp (%) 20 50 70 20 50 70

PP Hong 0.342 0.654 0.798 0.414 0.685 0.789

Trong thử nghiệm, độ thú vị của luật được tính theo công thức 2.5 trong mục 1.4.1. Từ kết quả trong Bảng 3.9 cho thấy độ thú vị trung bình của các luật kết hợp thu được của phương pháp sử dụng ĐSGT cao hơn hoặc sấp sỉ bằng hai phương pháp còn lại. 3.5.3. Phân tích và đánh giá kết quả thực nghiệm với biểu diễn dữ liệu dạng đa thể hạt Với mỗi thuộc tính trong CSDL được phân chia miền mờ sử dụng biểu diễn đa thể hạt và mỗi thuộc tính sử dụng một cấu trúc ĐSGT như trình bày trong mục 3.5.2.2.

A10 0.204 0.796 0.651 0.349

A4 0.548 0.452 0.457 0.543

A6 0.233 0.767 0.316 0.684

A7 0.202 0.798 0.800 0.200

A9 0.212 0.788 0.586 0.414

A8 0.200 0.800 0.798 0.202

Các kết quả thử nghiệm được so sánh với các kết quả đã công bố trước đây trong Bảng 3.10, thống kê số lượng tập phố biến với mỗ độ hỗ trợ khác nhau từ 20% đến 80%. Bảng 3.11 là kết quả thử nghiệm với ba phương pháp: phương pháp đề xuất sử dụng biểu diễn đa thể hạt, phương pháp biểu diễn đơn thể hạt đề xuất trong chương 3 và phương pháp Herrera (2009). Kết quả cho thấy phương pháp sử dụng biểu diễn Đa thể hạt cho số lượng 1-ItemSet tốt hơn số với hai phương pháp còn lại (như Hình 4.3). Ở đây, (liệt kê các thuộc tính dùng so sánh: độ phủ, chồng lấn đã trình bày ở trong mục 3.3.3) và các phương pháp dùng để so sánh đều thực hiện với biểu diễn đơn thể hạt. Các kết quả thử nghiệm cho thấy ưu việt của việc sử dụng biểu diễn đa thể hạt và ĐSGT, củng cố thêm cho các kết quả nghiên cứu liên quan đến sử dụng biểu diễn đa thể hạt (một số công trình công bố trong một số năm gần đây sử dụng biểu diễn đa thể hạt [37, 66-68, 82, 84])

𝜇(𝐿) 𝜇(𝑉) 𝑓𝑚(𝐶−) 𝑓𝑚(𝐶+)

A2 A5 0.531 0.203 0.208 0.797 0.469 0.792 0.501 0.202 0.617 0.798 0.499 0.383 Bảng 3.11: Quan hệ giữa số lượng tập mục và độ hỗ trợ tối thiểu 70 22 187 772 1774 2528

Min Support (%) 1-itemset 2-itemset 3-itemset 4-itemset 5-itemset

20 59 974 8890 50242 187379

30 50 675 4806 20719 57461

50 29 371 2660 11890 34995

60 26 285 2518 4708 9506

80 17 78 150 167 167

40 38 456 3111 13095 36432 Có thể thấy là dùng biểu diễn đa thể hạt sẽ cho kết quả tốt hơn hẳn. Ngoài ra, như đã nói ở trên, về mặt ngữ nghĩa, dùng biểu diễn đa thể hạt sẽ cho chúng ta các luật mang tính khái quát cao và các luật chi tiết. Luận án tiến hành thử nghiệm phương pháp của Herrera với việc phân chia như vậy, kết quả tuy có tăng về chỉ số nhưng vẫn kém phương pháp đề xuất (xem đồ thị so sánh Hình 3.27:). Cần nhấn mạnh rằng, với phương pháp luận án đề xuất, việc tính toán liên quan đến biểu diễn đa thể hạt là tăng thêm không đáng kể về mặt phức tạp cũng như mặt thời gian mà kết quả nhận được lại tốt hơn rất nhiều.

Bảng 3.10: Các tham số mờ của các ĐSGT được tối ưu của 10 thuộc tính với phương pháp sử dụng biểu diễn đa thể hạt A3 0.445 0.555 0.562 0.438

Hình 3.28: Tập hàm thuộc thu được sau khi thực hiện GA với phương pháp sử dụng biểu diễn đa thể hạt và ĐSGT Bảng 3.12: Quan hệ giữa số lượng 1-itemset và độ hỗ trợ tối thiểu

Min Support (%) PP biểu diễn Đa thể hạt PP biểu diễn Đơn thể hạt PP Herrera và cộng sự 20 54 21 25 30 46 17 21 40 35 13 15 50 27 8 10 60 23 7 5 70 14 6 3 80 12 3 2 90 5 1 0

Trong bảng 3.7 là các tham số mờ của các ĐSGT của 10 thuộc tính số thu được sau khi chạy giải thuật di truyền. Các tham số này được sử dụng để xây dựng các hàm thuộc theo dạng biểu diễn đa thể hạt như đã trình bày trong mục 3.2.2.

Hình 3.18 tập các hàm thuộc biểu diễn dạng đa thể hạt của 10 thuộc tính thu được sau khi thực hiện tối ưu bằng giải thuật GA. Có thể thấy các hàm thuộc được xây dựng dựa trên ĐSGT của các thuộc tính có phân bố khá tốt, đảm bảo độ bao phủ toàn miền giá trị và độ chồng lấn hợp lý. 3.6. Kết luận chương 3

Chương này luận án đề xuất phương pháp khai khá luật kết hợp mờ sử dụng ĐSGT dựa trên cơ sở phân chia mờ miền giá trị thuộc tính với biểu diễn đơn thể hạt và đa thể hạt. Với mỗi thuộc tính số sẽ sử dụng một cấu trúc ĐSDT để xây dựng các hàm thuộc dạng đơn thể hạt hoặc đa thể hạt. Luận án sử dụng giải thuật di truyền để tìm kiếm các thuộc tối ưu (hay xác định các tham số của các cấu trúc ĐSGT) dựa trên CSDL cho trước. Kết quả nghiên cứu này cho thấy phương pháp xây dựng các tập hàm thuộc để phân chia tập mục mờ trong bài toán khai phá luật kết hợp mờ, một công đoạn quan trọng mà còn ít được đầu tư nghiên cứu. Việc mở rộng ĐSGT (không chỉ có 5 hạng từ) để đáp ứng yêu cầu bài toán tối ưu hóa cả số lượng lẫn các thông số các MF đã nêu trên sẽ vừa giải quyết tốt bài toán khai phá dữ liệu, vừa phát huy thế mạnh của ĐSGT. Sử dụng ĐSGT có thể tăng dễ dàng số hạng từ mà vẫn đảm bảo có được các phân hoạch mạnh dùng phân chia miền xác định của mục. Nội dung của chương này được công bố trong các công trình [iii, iv].

Kết quả của luận án được thử nghiệm với 6 CSDL gồm: FAM95, pollution, stulong, liệu UCI từ kho dữ lấy basketball, quake, stock. Các CSDL này được (https://archive.ics.uci.edu).

Phương pháp này khá đơn giản nhưng hiệu quả trong việc xây dựng các tập mờ phân chia miền giá trị thuộc tính. Cách phân chia miền mờ vừa đảm bảo đáp ứng tốt các tiêu chí về hệ tập mờ, vừa mang lại sự đáp ứng tốt về mặt ngữ nghĩa cho các luật khai phá được. Luận án đã thử nghiệm với hai phương pháp biểu diễn dữ liệu: biểu diễn đơn thể hạt và biểu diễn đa thể hạt. Các luật khai phá được bao gồm cả các luật mang tính khái quát cao và các

luật chi tiết, phụ thuộc vào tầng biểu diễn dữ liệu trong cấu trúc đa thể hạt ta xây dựng thông qua ĐSGT.

KẾT LUẬN VÀ KIẾN NGHỊ

Với mục tiêu 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ờ, như luật kết hợp mờ, luật mờ dạng ngôn ngữ,… từ các kho dữ liệu số. Luận án sử dụng Đ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 mờ. Luận án đề xuất phương pháp nhằm giảm thời gian, cũng như đề xuất giải pháp tìm kiếm phân hoạch mờ tối ưu cho mỗi thuộc tính định lượng dựa vào CSDL đầu vào theo một số ràng buộc cho trước. Luận án đề xuất sử dụng lý thuyết ĐSGT và giải thuật GA áp dụng trong bài toán khai phá luật kết hợp mờ thay vì sử dụng lý thuyết tập mờ như các phương pháp đã đề xuất trước đây.

Kết quả nghiên cứu chính của luận án là: - Nhằm mục đích giảm thời gian khai phá luật kết hợp, luận án đề xuất phương pháp sử dụng ĐSGT và giải pháp nén CSDL mờ. Các giao dịch mờ gần nhau sẽ được gộp với nhau để tạo thành giao dịch mới. Ưu điểm của phương pháp này là giúp CSDL có kích thước nhỏ hơn CSDL ban đầu giúp thời gian khai phá luật kết hợp giảm.

- Luận án đề xuất sử dụng lý thuyết ĐSGT và giải thuật di truyền tìm kiếm hàm thuộc dựa vào CSDL giao dịch đầu vào và một số mục tiêu của bài toán khai phá luật kết hợp mờ. Phương pháp lập luận mờ sử dụng ĐSGT chỉ cần tập trung đến độ đo tính mờ hay tối ưu được bộ số gia tử, số lượng tham số ít hơn so với một số phương pháp đã đề xuất trước đây mà các tác giả sử dụng lý tuyết tập mờ giúp thời gian tối ưu nhanh hơn. Luận án sử dụng biểu diễn tập mờ dạng đơn thể hạt để tính toán độ thuộc của dữ liệu vào các miền mờ. Kết quả là chúng ta thu được tập các hàm thuộc cho các thuộc tính định lượng và tập các luật kết hợp mờ.

- Luận án sử dụng biểu diễn đa thể hạt và ĐSGT cho bài toán khai phá luật kết hợp mờ. Về mặt ngữ nghĩa, dùng biểu diễn đa thể hạt sẽ cho chúng ta các luật kết hợp vừa có tính khái quát và có tính chi tiết. Với phương pháp luận án đề xuất, việc tính toán liên quan đến biểu diễn đa thể hạt là tăng thêm không đáng kể về mặt phức tạp cũng như mặt thời gian mà kết quả nhận được lại tốt hơn rất nhiều.

Mặc dù luận án đã đạt được những kết quả khá tốt, tuy nhiên các kết quả nghiên cứu này chủ yếu tập trung vào giải pháp nén dữ liệu giao dịch và phân hoạch miền xác định của thuộc tính thành các miền mờ dưới dạng biểu diễn đơn thể hạt và đa thể hạt theo hướng tiếp cận sử dụng ĐSGT cho bài toán khai phá luật kết hợp mờ. Song, một số nội dung liên quan đến bài toán khai phá luật kết hợp cần được tiếp tục nghiên cứu hoàn chỉnh hơn: giải các bài toán tìm luật kết hợp phủ định, luật kết hợp có trọng số, luật kết hợp song song,… Đó là những vấn đề đặt ra cho chúng tôi cần phải có những nghiên cứu trong thời gian tới.