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:109

Thêm vào BST

Báo xấu

43
lượt xem 11
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à ghiê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. Cụ thể các biểu diễn dữ liệu đa thể hạt (Multi-granularity Representation of Data) được sử dụng, 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ủ đề:

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

Lưu

Nội dung Text: 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

BỘ GIÁO DỤC VÀ ĐÀO TẠO 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 LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – Năm 2020
BỘ GIÁO DỤC VÀ ĐÀO TẠO 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 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TSKH. Nguyễn Cát Hồ 2. TS. Trần Thái Sơn Hà Nội – Năm 2020
1 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Các kết quả trong luận án là trung thực và chưa từng được công bố trong bất kỳ công trình nào khác. Tác giả Nguyễn Tuấn Anh
2 LỜI CẢM ƠN Luận án được hoàn thành dưới sự hướng dẫn tận tình của PGS. TSKH. Nguyễn Cát Hồ và TS. Trần Thái Sơn. Lời đầu tiên, tác giả xin bày tỏ lòng kính trọng và biết ơn sâu sắc nhất tới hai thầy. Tác giả gửi lời cảm ơn chân thành tới Ban lãnh đạo Học viện Khoa học và Công nghệ, Viện Công nghệ thông tin, khoa Công nghệ thông tin và truyền thông đã tạo điều kiện thuận lợi trong quá trình học tập, nghiên cứu và hoàn thành luận án. Xin cảm ơn Ban giám hiệu trường Đại học Công nghệ thông tin và Truyền thông - ĐHTN, Ban chủ nhiệm khoa Công nghệ thông tin đã quan tâm giúp đỡ, tạo điều kiện tốt nhất trong công việc để tác giả có thời gian tập trung nghiên cứu. Cảm ơn các đồng nghiệp thuộc Khoa Công nghệ thông tin - Trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên, các anh chị trong nhóm nghiên cứu đại số gia tử đã động viên, khích lệ trao đổi những kiến thức và kinh nghiệm trong quá trình hoàn thành luận án. Cuối cùng, tác giả xin chân thành cảm ơn bố mẹ, chị em, đặc biệt là vợ và các con, những người luôn dành cho tác giả những tình cảm và chia sẻ những lúc khó khăn trong cuộc sống, luôn động viên giúp đỡ tác giả trong quá trình nghiên cứu. Luận án cũng là món quà tinh thần mà tác giả trân trọng gửi tặng đến các thành viên trong gia đình.
3 MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT..........................................5 DANH MỤC HÌNH BẢNG BIỂU ...........................................................................6 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ..................................................................7 MỞ ĐẦU ....................................................................................................................9 CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ ......................................................17 1.1. Tập mờ và các phép toán trên tập mờ ........................................................17 1.1.1. Tập mờ (fuzzy set) ...................................................................................17 1.1.2. Biến ngôn ngữ ..........................................................................................18 1.1.3. Phân hoạch mờ.........................................................................................19 1.2. Đại số gia tử ...................................................................................................21 1.2.1. Khái niệm Đại số gia tử ...........................................................................21 1.2.2. Một số tính chất của ĐSGT tuyến tính ....................................................22 1.2.3. Định lượng ngữ nghĩa của giá trị ngôn ngữ .............................................23 1.2.4. Khoảng mờ ..............................................................................................24 1.2.5. Độ đo tính mờ của các giá trị ngôn ngữ ..................................................25 1.3. Giải thuật di truyền ......................................................................................27 1.4. Bài toán khai phá luật kết hợp ....................................................................29 1.4.1. Một số khái niệm cơ bản..........................................................................29 1.4.2. Bài toán khai phá luật kết hợp mờ ...........................................................31 1.5. Một số hướng nghiên cứu về luật kết hợp ..................................................34 1.6. Kết luận chương 1 ........................................................................................37 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Ử ..................................................................................38 2.1. Đặt vấn đề ......................................................................................................38 2.2. Khai phá luật kết hợp mờ theo hướng tiếp cận ĐSGT .............................39 2.2.1. Mờ hóa cơ sở dữ liệu giao dịch ...............................................................39 2.2.2. Quan hệ khoảng cách giao dịch ...............................................................41 2.2.3. Xây dựng bảng định lượng ......................................................................42 2.3. Nén cơ sở dữ liệu giao dịch ..........................................................................43 2.4. Thuật toán trích xuất luật kết hợp mờ .......................................................46
4 2.5. Kết quả thử nghiệm ......................................................................................48 2.5.1. Thử nghiệm với CSDL FAM95...............................................................48 2.5.2. Thử nghiệm với CSDL STULONG ........................................................51 2.6. Kết luận chương 2 ........................................................................................54 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 ................................................................................56 3.1. Phân hoạch cho miền giá trị của thuộc tính ...............................................56 3.1.1. Đặt vấn đề ................................................................................................56 3.1.2. Rời rạc hóa thuộc tính định lượng ...........................................................57 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ờ ...........................................................................................................................60 3.2. Phương pháp phân hoạch mờ bằng biểu diễn thể hạt với ĐSGT ............63 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 ..........64 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 ............66 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.........................................................................................................................70 3.3.1. Mô hình giải thuật di truyền CHC ...........................................................71 3.3.2. Mã hóa tập các MF ..................................................................................72 3.3.3. Đánh giá nhiễm sắc thể ............................................................................73 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 ...................75 3.5. Kết quả thử nghiệm ......................................................................................77 3.5.1. Cơ sở dữ liệu sử dụng trong thử nghiệm .................................................77 3.5.2. Phân tích và đánh giá kết quả thử nghiệm với biểu diễn dữ liệu dạng đơn thể hạt .................................................................................................................78 3.5.3. Phân tích và đánh giá kết quả thử nghiệm với biểu diễn dữ liệu dạng đa thể hạt .................................................................................................................93 3.6. Kết luận chương 3 ........................................................................................97 KẾT LUẬN VÀ KIẾN NGHỊ ................................................................................99 CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN ...........................................................................................................................101 TÀI LIỆU THAM KHẢO ....................................................................................102
5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Các ký hiệu 𝒜𝒳 Đại số gia tử tuyến tính 𝒜𝒳 ∗ Đại số gia tử tuyến tính đầy đủ 𝜇 (ℎ ) Độ đo tính mờ của gia tử h 𝑓𝑚(𝑥) Độ đo tính mờ của gia tử x 𝑣 (𝑥 ) Hàm định lượng của giá trị ngôn ngữ của biến x 𝜇𝐴 (𝑥) Hàm xác định độ thuộc của giá trị x vào tập mờ A 𝑙 (𝑥 ) Độ dài của từ ngôn ngữ x ℑ𝑓𝑚 Khoảng tính mờ của giá trị ngôn ngữ 𝑋𝑘 Tập các hạng từ có độ dài đúng bằng k 𝑋(𝑘) Tập các hạng từ có độ dài ≤ 𝑘 Các từ viết tắt AR Luật kết hợp (association rule) DB, CSDL Cơ sở dữ liệu ĐLNN Định lượng ngữ nghĩa ĐSGT Đại số gia tử FRBS Fuzzy Rule-based Systen GA Giải thuật di truyền (Genetic Algorithms) KB Knowledge Base MF Hàm thuộc (Membership function) RB Fuzzy-based SQM Semantically Quantifying Mapping Min Supp Độ hỗ trợ tối thiểu
6 DANH MỤC HÌNH BẢNG BIỂU Bảng 2.1: Cơ sở dữ liệu ví dụ ...................................................................................41 Bảng 2.2: Mờ hóa dữ liệu trong Bảng 2.1 ................................................................41 Bảng 2.3: Bảng định lượng của cơ sở dữ liệu Bảng 2.2 ...........................................43 Bảng 2.4: Số lượng luật kết hợp thu được với độ tin cậy 80% .................................48 Bảng 2.5: Luật kết hợp thu được với độ hỗ trợ 60% và độ tin cậy 80% ..................49 Bảng 2.6: Luật kết hợp thu được với độ hỗ trợ 70% và độ tin cậy 80% ..................49 Bảng 2.7: Số lượng luật kết hợp thu được với độ tin cậy 80% .................................51 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% ....52 Bảng 2.9: Luật kết hợp thu được với độ hỗ trợ 85% và độ tin cậy 80% ..................52 Bảng 2.10: Luật kết hợp thu được với độ hỗ trợ 90% và độ tin cậy 80% ................53 Bảng 3.1: CSDL thống kế dân số của 10 gia đình ....................................................58 Bảng 3.2: Rời rạc hóa thuộc tính định lượng ............................................................58 Bảng 3.3: Ví dụ rời rạc hóa thuộc tính "Tuổi" ..........................................................59 Bảng 3.4: CSDL thử nghiệm ....................................................................................77 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...........................................................................78 Bảng 3.6: Kết quả thử nghiệm biểu diễn đơn thể hạt ...............................................79 Bảng 3.7: Quan hệ giữa độ thú vị trung bình của các luật ........................................82 Bảng 3.8: Bảng số lượng tập phổ biến 1-ItemSet .....................................................86 Bảng 3.9: Bảng Độ thú vị trung bình ........................................................................90 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................................................................94 Bảng 3.11: Quan hệ giữa số lượng tập mục và Min supp .........................................94 Bảng 3.12: Quan hệ giữa số lượng 1-ItemSet và Min Supp .....................................95
7 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Hàm thuộc cho tập mờ thể hiện tuổi người là: Trẻ, Trung niên, Già .......19 Hình 1.2: Một cấu trúc phân hoạch mờ dạng đơn thể hạt .........................................20 Hình 1.3: Một cấu trúc phân hoạch mờ dạng đa thể hạt ...........................................20 Hình 1.4: Khoảng tính mờ của các hạng từ của biến TRUTH .................................25 Hình 1.5: Độ đo tính mờ của biến TRUTH ..............................................................26 Hình 1.6: Lưu đồ giải thuật di truyền .......................................................................28 Hình 2.1: Xây dựng phân hoạch mờ dựa trên ĐSGT ...............................................40 Hình 2.2: Tổng quan về thuật toán nén CSDL giao dịch ..........................................43 Hình 2.3: Thời gian thực hiện với CSDL nén và CSDL không nén .........................50 Hình 2.4: Thời gian thực hiện với CSDL nén ...........................................................50 Hình 2.5: Thời gian thực hiện với CSDL nén và CSDL không nén .........................54 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 ........................................................................................................................65 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 ....65 Hình 3.3: Cấu trúc hạt thể nhiều mức .......................................................................67 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 ......69 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 ........................................................................................................70 Hình 3.6: Mô hình giải thuật di truyền CHC ............................................................72 Hình 3.7: Tập các MF cho mục Ij ......................................................................74 Hình 3.8: Hai tập hàm thuộc phân bố không tốt ................................................75 Hình 3.9: Quan hệ giữa độ phù hợp (Suit) của các hàm thuộc và Min Supp ...........80 Hình 3.10: Quan hệ giữa giá trị hàm mục tiêu và Min Supp ....................................81 Hình 3.11: Quan hệ giữa độ hỗ trợ tập mục 1-ItemSet và Min Supp .......................81 Hình 3.12: Quan hệ giữa số lượng 1-ItemSet và Min Supp .....................................82 Hình 3.13: Quan hệ giữa độ thú vị trung bình và Min Supp ....................................83
8 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ờ..............................................................................85 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 .................................................................................86 Hình 3.16: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL Pollution ....88 Hình 3.17: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL Stulong ......88 Hình 3.18: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL Basketball ..89 Hình 3.19: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL Quake ........89 Hình 3.20: Quan hệ giữa số lượng 1-ItemSet và Min Supp với CSDL stock ..........90 Hình 3.21: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Pollution ..91 Hình 3.22: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Stulong ....92 Hình 3.23: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Basketball 92 Hình 3.24: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Quake ......92 Hình 3.25: Quan hệ giữa Độ thú vị trung bình và Min Supp với CSDL Stock ........93 Hình 3.26: Quan hệ giữa số lượng tập phố biến và Min Supp .................................95 Hình 3.27: So sánh số lượng tập phổ biến và Min Supp ..........................................95 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 ...................................................................................97
9 MỞ ĐẦU Cùng với sự phát triển mạnh mẽ của Công nghệ thông tin, đặc biệt là các hệ thống thông tin quản lý giai đoạn vừa qua, xuất hiện rất nhiều các kho thông tin hay CSDL lớn hoặc rất lớn. Để khai thác thông tin ẩn trong các kho dữ liệu kích cỡ lớn như vậy nhằm phục vụ cho các nhu cầu quản lý cũng như cho các hoạt động khoa học khác nhau (như trí tuệ nhân tạo,..), hướng nghiên cứu khai phá dữ liệu, phát hiện tri thức đã ra đời thu hút sự quan tâm của các nhà tin học cũng như các chuyên gia trong nhiều lĩnh vực khác nhau như y tế, giáo dục,… và phát triển mạnh mẽ trong thời gian gần đây. Vài thí dụ có thể thấy: - Phát hiện những mối quan hệ dữ liệu, các luật kết hợp trong các kho dữ liệu lớn như các CSDL, các kho dữ liệu giao dịch bán hàng trong siêu thị, các kho dữ liệu phản ảnh một phạm vi nào đó của hoạt động kinh tế - xã hội. - Giải quyết vấn đề trích rút thông tin trong tập dữ liệu lớn dạng các câu tóm tắt ngôn ngữ (Linguistic summaries). Bài toán khai thác luật kết hợp (Association rule mining) 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. Giai đoạn đầu, các nghiên cứu trước đây được giới hạn trong phạm vi “bài toán luật kết hợp cổ điển”, tức là chỉ làm việc với các kho dữ liệu có giá trị nhị phân (0 và 1), sau đó mở rộng ra dữ liệu nằm trong trường số thực. Trong những năm gần đây nhiều giải thuật dùng cho những công việc đặc thù đã đượ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 kết hợp, 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 kết hợp vì ta thấy không phải luật kết hợp nào khai phá được cũng có ý nghĩa đối vời người sử dụng. Có rất nhiều thuật toán đã được đề xuất để tìm kiếm luật kết hợp từ CSDL có thuộc tính định lượng. Dạng khai phá luật kết hợp đầu tiên được đề xuất là luật kết hợp nhị phân dựa trên dữ liệu basket đã được Agrawal và cộng sự đề xuất [21]. Ở đây CSDL là một bảng các giao dịch tại một siêu thị trong ngày chẳng hạn với các cột là các mục (hàng hóa) và các dòng là danh sách người mua. Nếu người A mua hàng ở
10 các mục x, y, z,… thì tại đó, CSDL nhận giá trị 1, còn lại là nhận giá trị 0. Như vậy, bài toán khai phá dữ liệu ban đầu làm việc với các giá trị nhị phân. Một luật kết hợp có dạng R: "𝑁ế𝑢 𝑋 𝑡ℎì 𝑌", trong đó X, Y là tập các mục, 𝑋, 𝑌 ⊆I và X ∩Y = ∅, X được gọi là tiên đề, Y được gọi là hệ quả của luật. Hai độ do quan trọng và thường được sử dụng trong bài toán khai phá luật kết hợp là: Độ hỗ trợ (support) và Độ tin cậy (confidence). Với CSDL nhị phân chỉ quan tâm là một mặt hàng có xuất hiện trong giao dịch hay không mà không quan tâm đến số lượng mặt hàng trong mỗi giao dịch. Trong thực tế CSDL thương bao gồm có cả các thuộc tính định lượng, các thuật toán khai phá luật kết hợp với dữ liệu nhi phân không thể áp dụng với CSDL dạng này. Để có thể xử lý dữ liệu kiểu này, phương pháp thường được sử dụng là chia miền giá trị của các thuộc tính định lượng đó thành các khoảng, sau đó chuyển CSDL thành CSDL mới để có thể áp dụng các thuật toán khai phá luật kết hợp nhị phân [8]. Luật kết hợp này có dạng: Nếu Tuổi ∈ [1, 25] thì Thu nhập ∈ [2 triệu, 3 triệu]. Với phương pháp rời rạc dữ liệu này đã giải quyết được bài toán chuyển từ CSDL giao dịch với dữ liệu số về dữ liệu giao dịch nhị phân, tuy nhiên với kết quả này cũng chưa thỏa mãn các nhà nghiên cứu. Một cách tự nhiên, điều này dẫn đến việc đề xuất và nghiên cứu các luật kết hợp mờ, ở đó người ta phân chia miền xác định của thuộc tính bằng các tập mờ. Trong [29-31, 57], thuật toán khai phá luật kết hợp mờ đã được đề xuất. 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. Để khai phá luật kết hợp mờ với CSDL có các thuộc tính định lượng, đầu tiên phải phân hoạch miền giá trị của các thuộc tính thành các miền mờ (mỗi miền mờ gắn với một nhãn ngôn ngữ). Trong lý thuyết tập mờ, mỗi miền mờ như vậy được coi là một tập mờ và ứng với một hàm thuộc (Membership Function -MF) nhằm xác định độ “thuộc” của giá trị biến vào tập mờ đã cho. Hàm thuộc xác định độ thuộc của một đối tượng vào mỗi tập mờ đã được định nghĩa trước cho các thuộc tính định lượng. Khi đó, mỗi giá trị của một thuộc tính trong CSDL sẽ ứng với một tập các giá trị của
11 các hàm thuộc ứng với các tập mờ của thuộc tính đó và ta sẽ xử lý tập giá trị độ thuộc này thay cho xử lý bản thân giá trị đó của CSDL. Thuật toán khai phá luật kết hợp mờ đề xuất trong [30], thuật toán khai phá luật kết hợp mờ theo trình tự sau: người sử dụng hoặc chuyên gia phải cung cấp thuật toán cùng với các tập mờ cho các thuộc tính định lượng và các hàm thuộc. Các hàm thuộc và tập mờ được cung cấp dựa vào kinh nghiệm của các chuyên gia, có thể không phù hợp với luật kết hợp mờ của CSDL. Để có được các luật kết hợp chất lượng, một trong các hướng nghiên cứu đực các tác giả đề xuất là dựa vào CSDL giao dịch đầu vào trích chọn ra các hàm thuộc. Trong các nghiên cứu về khai phá tri thức, bài toán phân chia miền xác định các thuộc tính định lượng của dữ liệu ngày càng nhận được sự quan tâm rộng rãi. 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 về sau cho hầu hết các bài toán khai phá tri thức như: khai phá luật kết hợp, phân loại, nhận dạng, hồi quy [15, 16, 28, 52, 67],... Trong các năm 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. Nếu không có một hệ các MF được xây dựng tốt thì cũng sẽ không thể trích xuất các luật kết hợp tốt được. Nếu ta có một sự phân chia mờ hợp lý (theo một số tiêu chuẩn xác định), các tri thức khai phá được về sau cũng sẽ là các tri thức phản ánh đúng đắn hơn các quy luật ẩn trong kho thông tin. Ngược lại, nếu ban đầu không có sự phân chia mờ hợp lý, tri thức khai phá được có thể sẽ mang nặng tính chủ quan, áp đặt, không đúng với bản chất sự việc. Đây thật ra là bài toán không đơn giản dù cho bề ngoài của sự việc không cho thấy rõ điều đó. Bài toán phức tạp trước hết vì liên quan đến nhận thức mang tính cảm tính của cá nhân, phụ thuộc nhiều vào ngữ cảnh, chẳng hạn trong miền thuộc tính “khoảng cách” thì khoảng cách bao nhiêu gọi là “xa”, là “tương đối gần”,... Thứ nữa, việc phân chia mờ cũng phụ thuộc rất nhiều vào dữ liệu đầu vào mà ta có được. Một số nghiên cứu có giả thiết về hàm phân bố xác suất của dữ liệu hoặc các giả thiết khác. Tuy nhiên dữ liệu thì rất đa dạng, các giả thiết không phải lúc nào cũng thỏa mãn và khối lượng thông tin thì vô cùng lớn, đòi hỏi phải có các phương pháp tin cậy nhưng không quá phức tạp để có thể xử lý thông tin trong thời gian chấp nhận được.
12 Phương pháp tiếp cận theo lý thuyết tập mờ cho ta một cách xử lý dữ liệu khá mềm dẻo, nhanh chóng so với các phương pháp xử lý số cổ điển. Tuy vậy, vẫn còn nhiều vấn đề đặt ra như việc phân chia các miền mờ thế nào cho hợp lý, việc gắn nhãn ngôn ngữ vào các miền mờ thường dựa vào trực quan của con người, làm sao xây dựng được các MF nhanh chóng, phù hợp và cách xử lý các MF này thế nào để giữ được ngữ nghĩa gắn với chúng,... Rất nhiều thuật toán khai phá luật kết hợp mờ đã được đề xuất [27, 31, 57, 59, 61, 65] với các phương pháp này thường định nghĩa trước các hàm thuộc, điều này khó trong thực tế và thương mang ý chủ quan của con người Một số công bố được các nhà nghiên cứu đề xuất phương pháp tìm kiếm hàm thuộc và ứng dụng trong bài toán khai phá luật kết hợp từ CSDL có các thuộc tính định lượng: Tzung-Pei Hong và cộng sự (2004) [83], (2008) [42], (2016) [46], (2018) [60]; Herrera và cộng sự (2009) [53], (2015) [22]; Harikesh Bahadur Yadav và cộng sự (2015) [14]; Aashna Agarwal và cộng sự (2016) [7]; Hemant Kumar Soni và cộng sự (2016) [38]; Harihar Kalia và cộng sự (2016)[74]; Umesh Kumar Patel và cộng sự (2016) [76]; Umit Can và cộng sự (2017) [9], Archana Gupta và cộng sự (2019) [75]. Ý tưởng chính của các phương pháp sử dụng giải thuật GA để tìm kiếm trong CSDL các hàm thuộc từ CSDL sau đó áp dụng hàm thuộc tìm kiếm được để khai phá luật kết hợp. Hướng nghiên cứu này đã cho phép xây dựng tập các hàm thuộc tốt hơn, không phải dựa hoàn toàn trên cách nhìn chủ quan của các chuyên gia. Tuy vậy, do tập các hàm thuộc tương ứng với các tập mờ con dùng để phân chia miền xác định của thuộc tính có điểm xuất phát ban đầu chưa thực sự tốt nên kết quả thu được qua giải thuật di truyền chưa thật sự tối ưu (chẳng hạn như độ chồng lấn còn cao, tính đáng quan tâm, hay ngữ nghĩa của các luật thu được chưa thật sự đáp ứng yêu cầu – mà ta sẽ thấy qua phân tích các kết quả thử nghiệm về sau). Để khắc phục một số hạn chế của hướng tiếp cận dựa trên lý tuyết tập mờ, N.C.Ho và Wechler đã đề xuất hướng tiếp cận tính toán đựa trên ngôn ngữ gọi là ĐSGT [19, 49]. Với cấu trúc của ĐSGT cho phép ngữ nghĩa tính toán của từ được định nghĩa dựa trên thứ tự ngữ nghĩa vốn có của các từ của biến, các miền của từ của các biến thiết lập một cấu trúc dựa trên thứ tự là đủ để giải các bài toán thực tế. Việc gán ngữ nghĩa tính toán cho các từ của một biến bằng các tập mờ được xem như làm một ánh xạ. Với phương pháp này, chỉ cần một bộ độ đo tính mờ của các từ của một
13 biến là đủ để xác định các đặc tính định lượng khác nhau như: giá trị định lượng ngữ nghĩa, các khoảng mờ,… Với các tiếp cận sử dụng ĐSGT cho phép dễ dàng phân hoạch miền giá trị của các thuộc tính thành các miền mờ dựa vào khoảng tính mờ và giá trị định lượng ngữ nghĩa của các từ. Từ đó, có dễ dàng xây dựng được các hàm thuộc đựa trên hoạch đã có. Các hàm thuộc này được xây dựng dựa trên một cấu trúc ĐSGT vì vậy các hàm thuộc có sự ràng buộc với nhau và gắn với một nhãn ngôn ngữ. Các phân hoạch dựa trên các miền mờ con theo cách tiếp cận ĐSGT còn là một phân hoạch mạnh, có nghĩa một giá trị bất kỳ của miền xác định thuộc tính đều có tổng các độ thuộc vào các hàm thuộc phân chia miền xác định của thuộc tính đó bằng 1. Để khắc phục nhược điểm của lý thuyết tập mờ, một số giải pháp đã ứng dụng ĐSGT vào giải quyết bài toán khai phá luật kết hợp mờ [2, 3]. Nguyễn Công Hào và cộng sự (2012) [2] xem miền trị Dom(A) của thuộc tính mờ là một cấu trúc ĐGST. Với mỗi x ∈ Dom(A) sẽ tương ứng với mỗi phần tử y trong ĐSGT (sử dụng hàm ngược trong ĐSGT). Phương pháp này đơn giản nhưng việc ứng mỗi giá trị của Dom(A) với chỉ một phần tử của ĐSGT có thể gây mất mát thông tin. Nguyễn Nam Tiến và cộng sự (2012) [3] giải quyết được hạn chế đó bằng cách xác định khoảng cách của x với giá trị định lượng ngữ nghĩa của hai phần tử gần x nhất về hai phía, còn các phần tử khác của ĐSGT bằng 0. Như vậy với mỗi giá trị x chúng ta lưu một cặp giá trị thay vì trong [2] chỉ lưu một giá trị. Bên cạnh hướng nghiên cứu tìm ra các luật kết hợp có ý nghĩa hơn, các nhà nghiên cứu cũng đề xuất nhiều giải pháp nhằm tăng tốc độ khai phá luật kết hợp: luật kết hợp song song, nén dữ liệu nên cây FP-Tree,… Jia-Yu Dai và cộng sự (2008) [18] đề xuất giải pháp nén CSDL nhị phân, giải pháp là gộp các giao dịch nhị phân tạo thành giao dịch mới giúp giảm kích thước CSDL giao dịch, Chien-Min Lin (2013) [5] đề xuất giải pháp nén CSDL giao dịch lên cây FP-tree, Chun-Wei Lin và cộng sự (2009) [34] đề xuất giải pháp nén CSDL giao dịch mờ lên cây FP-Tree. Với các hướng nghiên cứu về khai phá luật kết hợp mờ nếu trên, đa phần các nhà nghiên cứu sử dụng biểu diễn các tập mờ dạng đơn thể hạt. Trong một số năm gần đây nhiều nhà nghiên cứu đã nghiên cứu và sử dụng các hàm thuộc dạng đa thể hạt cho các bài toán trong khai phá dữ liệu [37, 66-68, 82, 84]. Đây là một lĩnh vực nghiên cứu ứng dụng rộng lớn. Nội dung nghiên cứu của luận án có tiếp cận cả hai hướng nghiên cứu (là nghiên cứu giảm thời gian tính toán
14 và tìm hiểu xây dựng các luật có ngữ nghĩa đáng quan tâm của các luật mờ) nhưng được giới hạn trong các hướng nhỏ: - 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ờ với thông tin ngôn ngữ (luật dạng ngôn ngữ) từ CSDL số nhằm phát hiện các quan hệ dữ liệu không dễ tiên lượng, nhưng có ích trong công việc quản lý, hay các tri thức luật mờ sử dụng trong lập luận,... - Đề xuất giải pháp nén dữ liệu giao dịch mờ nhằm tăng tốc độ khai phá luật kết hợp. Trong luận án 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 vì những lý do sau: (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 miền xác định của thuộc tính thành các miền mờ nhằm đưa ra các luật kết hợp có ý nghĩa. Trong khi đó, ĐSGT dựa trên một cấu trúc toán học rõ ràng hơn, do đó việc xây dựng tập các hàm thuộc xác định các miền mờ con dùng để phân chia miền xác định trở nên ít mang tính chủ quan hơn và ngữ nghĩa của luật sẽ trở nên dễ chấp nhận hơn. (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ý. Để nghiên cứu phát triển phương pháp, thuật toán phát hiện tri thức luật như vậy cần những nội dung nghiên cứu sau: - 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. Việc nghiên cứu này đòi hỏi nghiên cứu nắm vững một cách hệ thống thêm các kiến thức về lý thuyết tập mờ và ĐSGT, những cơ sở lý thuyết liên quan đến biểu thị ngữ nghĩa của các khái niệm mờ trong ngôn ngữ tự nhiên. - Một trong những ứng dụng quan trọng của tri thức luật là nó thiết lập cơ sở tri thức cho lập luận mờ hay lập luận xấp xỉ. Vì vậy, phương pháp luận phát hiện tri thức luật cũng gắn với phương pháp lập luận mờ: một hệ tri thức luật mờ là tốt, phù hợp nếu cơ sở tri thức luật được phát hiện tạo được cơ sở cho lập luận hiệu quả. Vì vậy các phương pháp lập luận mờ cũng là một nội dung nghiên cứu của đề tài. Nội dung
15 nghiên cứu này bao gồm nghiên cứu các phương pháp lập luận dựa trên lý thuyết tập mờ kết hợp với phương pháp dựa trên ĐSGT. - 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. Cụ thể các biểu diễn dữ liệu đa thể hạt (Multi-granularity Representation of Data) được sử dụng, phù hợp với sự chú ý ngày càng gia tăng của hướng nghiên cứu này. Kết quả của luận án: - Đề xuất phương pháp khai phá luật kết hợp mờ dựa trên tiếp cận sử dụng ĐSGT và giải pháp nén CSDL giao dịch. - Đề xuất phương pháp tìm kiếm hàm thuộc cho mỗi thuộc tính định lượng trong CSDL bằng phương pháp sử dụng lý thuyết ĐSGT và giải thuật GA. Các hàm thuộc trong phương pháp này được xây dựng dựa trên biểu diễn dữ liệu đơn thể hạt và đa thể hạt. Bố cục luận án bao gồm: Phần mở đầu, 3 chương, phần kết luận và tài liệu tham khảo. Kết quả chính của luận án tập trung ở chương 2, và 3. Cụ thể: Chương 1: Trình bày những kiến thức cơ sở cần thiết làm nền tảng trong quá trình nghiên cứu và những đề xuất mới của luận án, Các khái niệm của lý thuyết tập mờ như: tập mờ, phương pháp xây dựng tập mờ, biến ngôn ngữ, phân hoạch mờ. Trình bày những nội dung cơ bản của lý thuýet ĐSGT như: khái niệm ĐSGT, ĐSGT tuyến tính, ĐSGT tuyến tính đầy đủ, độ đo tính mờ, hàm định lượng ngữ nghĩa. Trình bày tóm tắt về về bài toán khai phá luật kết hợp và một số khái niệm cơ bản liên quan đến bài toán khai phá luật kết hợp. Chương 2: Phát triển thuật toán theo hướng tiếp cận ĐSGT cho bài toán khai phá luật kết hợp mờ. Thay vì cách tiếp cận như truyền thống là sử dụng lý thuyết tập mờ, luận án sử ĐSGT để mờ hoá CSDL giao dịch, mỗi một thuộc tính định lượng sẽ sử dụng một cấu trúc ĐSGT. Để giảm thời gian khai phá luật kết hợp, chương này đề xuất giải pháp nén CSDL giao dịch mờ nhằm giảm kích thước CSDL. Định nghĩa quan hệ và khoảng cách giữa các giao dịch được đề xuất, từ đó các giao dịch có khoảng cách gần nhau sẽ được gộp lại với nhau. Do kích thước CSDL thu được nhỏ hơn kích thước CSDL ban đầu, giúp cho thời gian khai phá giảm.
16 Chương 3: Việc phân chia miền giá trị của các thuộc tính định lượng có ý nghĩa quan trọng và ảnh hưởng đến ý nghĩa của các luật kết hợp trong bài toán khai phá luật kết hợp mờ. Trong chương này, luận án sử dụng lý thuyết ĐSGT, mỗi thuộc tính định lượng sử dụng một ĐSGT. Dựa vào giá trị định lượng ngữ nghĩa của các phần tử ĐSGT và khoảng tính mờ để xây dựng các hàm thuộc cho các thuộc tính định lượng. Chúng ta sử dụng biểu diễn đơn thể hạt và đa thể hạt để xây dựng các hàm thuộc cho các thuộc tính, các hàm thuộc có dạng hình tam giác. Nhằm mục đích thu được các luật kết hợp có ý nghĩa, luận án sử dụng giải thuật GA để tìm ra các tham số của ĐSGT. 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.
17 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ờ Lý thuyết tập mờ được Zadeh thiết lập lần đầu năm 1965 trong [40]. Khái niệm tập mờ là một mở rộng của lý thuyết tập hợp cổ điển và được dùng trong lôgic mờ. Trong lý thuyết tập hợp cổ điển, quan hệ thành viên của các phần tử trong một tập hợp được đánh giá theo kiểu nhị phân theo một điều kiện rõ ràng - một phần tử hoặc thuộc hoặc không thuộc về tập hợp. Mở rộng ra trong lý thuyết tập mờ, ngữ nghĩa của mỗi từ mờ được biểu diễn bằng một hàm từ tập vũ trụ U vào đoạn [0, 1] và hàm đó gọi là tập mờ trên U. Với tập mờ thì bất kỳ phần tử nào trong vũ trụ đều có thể thuộc về nó với mực độ thuộc được đo bởi một giá trị trong đoạn [0, 1]. 1.1.1. Tập mờ (fuzzy set) Định nghĩa 1.1: [40] 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ự (x, μA (x)), với μA (x) là hàm từ U vào [0, 1] gán cho mỗi phần tử x thuộc U giá trị μA (x) phản ảnh mức độ thuộc của x thuộc vào tập mờ A. Nếu 𝜇𝐴 (𝑥) = 0 thì ta nói x hoàn toàn không thuộc tập A, ngoài ra nếu 𝜇𝐴 (𝑥) = 1 thì ta nói x thuộc hoàn toàn vào A. Trong Định nghĩa 1.1, hàm 𝜇 còn được gọi là hàm thuộc (membership function). Khi xây dựng các hàm thuộc của tập mờ A nào đó, một yêu cầu đặt ra là giá trị của nó phải biến thiên từ 0 đến 1. Trong các ứng dụng lý thuyết tập mờ ta thường sử dụng một số dạng hàm thuộc dưới đây cho tập mờ A: 𝑥−𝑎 𝑐−𝑥 Hàm thuộc dạng tam giác: 𝜇𝐴 (𝑥) = 𝑚𝑎𝑥 (𝑚𝑖𝑛 ( , ) , 0). Trong đó a, b, 𝑏−𝑎 𝑐−𝑏 c lần lượt là chân bên trái, đỉnh và chân bên phải của tam giác. 𝑥−𝑎 𝑑−𝑥 Hàm thuộc dạng hình thang: 𝜇𝐴 (𝑥) = 𝑚𝑎𝑥 (𝑚𝑖𝑛 ( , , 1) , 0). Trong đó 𝑏−𝑎 𝑑−𝑐 a, d lần lượt là đỉnh dưới bên trái, bên phải, b, c lần lượt là đỉnh trên bên trái, bên phải của hình thang. −(𝑏−𝑥)2 Hàm thuộc Gauss: 𝜇𝐴 (𝑥) = 𝑒 2𝑐2 . Trong đó c là độ rộng và b là vị trí đỉnh của hàm. Trong các dạng hàm thuộc của các tập mờ ở trên, hàm thuộc dạng tam giác được sử dụng nhiều nhất do nó đơn giản và dễ hiểu với người dùng.
18 Các khái niệm, tính chất, phép toán trong lý thuyết tập kinh điển cũng được mở rộng cho các tập mờ [1, 35, 41]. Theo đó, các phép toán như t-norm, t-conorm, negation và phép kép theo,... trong logic mờ được đề xuất, nghiên cứu chi tiết cung cấp cho các mô hình ứng dụng giải các bài toán thực tế. 1.1.2. Biến ngôn ngữ Biến ngôn ngữ là một biến có thể gán các từ trong ngôn ngữ cho giá trị của nó. Các từ được đặc trưng bởi định nghĩa tập mờ trong miền xác định mà ở đó biến được định nghĩa. Các biến ngôn ngữ cho phép biểu diễn một miền các giá trị số dưới dạng thuật ngữ miêu tả đơn giản của hệ mờ. Ví dụ: tuổi của con người có thể xem đây là biến ngôn ngữ có tên gọi TUỔI và nó nhận các giá trị ngôn ngữ như: “già”, “rất già”, “trung bình”, “trẻ”, ”rất trẻ”,... Tương ứng với mỗi hàm thuộc sẽ được gán một giá trị ngôn ngữ. Giả sử lấy giới hạn của tuổi thông thường trong khoảng [1, 120] và giả sử rằng các giá trị ngôn ngữ được sinh ra bởi một tập các luật. Khi đó, một cách hình thức, chúng ta có định nghĩa của biến ngôn ngữ sau đây: Định nghĩa 1.2: [13] Biến ngôn ngữ là một bộ gồm năm thành phần (X,T(X), U, R, M), trong đó X là tên biến, 𝑇(𝑋 ) là tập các giá trị ngôn ngữ của biến X, U là không gian tham chiếu của biến cơ sở u, mỗi giá trị ngôn ngữ xem như là một biến mờ trên U kết hợp với biến cơ sở u, R là một qui tắc cú pháp sinh các giá trị ngôn ngữ cho tập 𝑇(𝑋 ), M là qui tắc ngữ nghĩa gán mỗi giá trị ngôn ngữ trong 𝑇(𝑋 ) với một tập mờ trên U. Ví dụ 1.1: Từ định nghĩa trên, nếu biến ngôn ngữ X là biến TUỔI, biến cơ sở của u có miền xác định là 𝑈 = [1,120] tính theo tuổi. Tập các giá trị ngôn ngữ tương ứng của biến ngôn ngữ là 𝑇(𝑇𝑈Ổ𝐼) = {𝑇𝑟ẻ, 𝑇𝑟𝑢𝑛𝑔 𝑛𝑖ê𝑛, 𝐺𝑖à}. R là một qui tắc để sinh ra các giá trị này. M là luật gán ngữ nghĩa sao cho mỗi một giá trị ngôn ngữ sẽ được gán với một tập mờ. Chẳng hạn, đối với giá trị nguyên thuỷ “già”, 𝑀(𝐺𝑖à) = {(𝑢, 𝜇𝐺𝑖à (𝑢))| 𝑢 ∈ [1,120]}, được gán như sau: 0 𝑢 ≤ 40 𝑢 − 40 𝜇𝐺𝑖à (𝑢) = { 40 < 𝑢 ≤ 55 120 1 55 ≤ 𝑢