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. MỘT SỐ KIẾN THỨC CƠ SỞ 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].
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. 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ế. 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.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 ≤ 𝑢 19 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à 1. Phân hoạch mờ Chúng ta có định nghĩa phân hoạch mờ như sau: Định nghĩa 1.3: [36] Cho m điểm cố định 𝑝1 , 𝑝2 , … , 𝑝𝑚 thuộc tập 𝑈 = [𝑎, 𝑏] ⊂ 𝑅, 𝑝1 = 𝑎, 𝑝𝑚 = 𝑏 là không gian tham chiếu của biến cơ sở 𝑢 của biến ngôn ngữ 𝑋. Khi đó một tập 𝑇 gồm m tập mờ 𝐴1 , 𝐴2 , … , 𝐴𝑚 định nghĩa trên 𝑈 (với hàm thuộc tương ứng là 𝜇𝐴1 , 𝜇𝐴2 ,., 𝜇𝐴𝑚 ) được gọi là một phân hoạch mờ của 𝑈 nếu các điều kiện sau thoả mãn, ∀𝑘 = 1, … , 𝑚: 1) 𝜇𝐴𝑘 (𝑝𝑘 ) (𝑝𝑘 thuộc về phần được gọi là lõi của 𝐴𝑘 ); 2) Nếu x ∉ [𝑝𝑘−1 , 𝑝𝑘+1 ] thì 𝜇𝐴𝑘 (𝑥) = 0 (trong đó 𝑝0 = 𝑝1 = 𝑎 và 𝑝𝑝+1 = 𝑝𝑝 = 𝑏); 3) 𝜇𝐴𝑘 (𝑥) là liên tục; 4) 𝜇𝐴𝑘 (𝑥) đơn điệu tăng trên [𝑝𝑘−1 , 𝑝𝑘 ]; 5) ∀𝑥 ∈ 𝑈, ∃𝑘, sao cho 𝜇𝐴𝑘 (𝑥) > 0; Nếu phân hoạch mờ thoả mãn thêm điều kiện 6) dưới đây thì được gọi là phân hoạch mờ mạnh. 6) ∀𝑥𝜖𝑈, ∑𝑚 𝑘=1 𝜇𝐴𝑘 (𝑥 ) = 1; Nếu phân hoạch mờ thoả mãn thêm điều kiện 7), 8), 9) dưới đây thì được gọi là phân hoạch đều.
7) Với 𝑘 ≠ 𝑚 thì ℎ𝑘 = 𝑝𝑘+1 − 𝑝𝑘 = hằng số 8) Các tập mờ 𝜇𝐴𝑘 (𝑥) là hàm đối xứng 9) Các tập mờ 𝜇𝐴𝑘 (𝑥) có cùng một dạng hình học Mỗi phân hoạch mờ theo định nghĩa Định nghĩa 1.3 còn được gọi là một thể hạt (granularity), một phân hoạch mờ gồm một thể hạt gọi là phân hoạch mờ đơn thể 20 hạt (single granularity), một phân hoạch mờ gồm nhiều thể hạt gọi là phân hoạch mờ đa thể hạt (multi granularity).2: Một cấu trúc phân hoạch mờ dạng đơn thể hạt Để thiết kế các phân hoạch mờ, chúng ta có thể tiếp cận theo hai hướng: lý thuyết tập mờ và tiếp cận theo lý thuyết ĐSGT [19, 49]. Theo tiếp cận lý thuyết tập mờ việc thiết kế phân hoạch mờ là đi xác định các tập mờ cho mỗi phân hoạch rồi gắn cho nó một nhãn ngôn ngữ. Quá trình thiết kế tập mờ không xuất phát từ ngữ nghĩa của từ ngôn ngữ và không có ràng buộc liên kết giữa nhãn ngôn ngữ và tập mờ. Theo tiếp cận lý thuyết ĐSGT khắc phục được một số nhước điểm của lý thuyết tập mờ, việc thiết kế phân hoạch mờ là đi xác định các từ ngôn ngữ và ngữ nghĩa của từ sử dụng trong phân hoạch.3: Một cấu trúc phân hoạch mờ dạng đa thể hạt Quá trình này được thực hiện dựa trên ngữ nghĩa của miền ngôn ngữ và dựa trên hệ hình thức hóa của ĐSGT.
Phương pháp thiết kế phân hoạch sử dụng ĐSGT phù hợp với cấu trúc vốn có của ngôn ngữ tự nhiên.2 là một cấu trúc phân hoạch mờ dạng đơn thể hạt, Hình 1.3 là một cấu trúc phân hoạch mờ dạng đa thể hạt. Thiết kế phân hoạch miền giá trị của các thuộc tính sử dụng biểu diễn dạng đa thể hạt có ưu điểm là các từ có ngữ nghĩa từ khái quát đến đặc tả. Vì vậy nó phù hợp với ngữ nghĩa vốn có của từ trong thế thế giới thực hơn. Đại số gia tử Để hiểu ý nghĩa của ĐSGT ta hãy lấy biến số 𝑥𝑁 nhận giá trị số thực trên một khoảng [a, b], định ý biến tốc độ chẳng hạn.