Chương 1: Cơ sở lý thuyết: trình bày các lý thuyết liên quan sử dụng trong đồ án Chương 2: Đồ thị tri thức mờ: trình bày về mô hình đồ thị tri thức mờ, cách biểu diễn đồ thị tri thức mờ, suy diễn trên đồ thị tri thức mờ Chương 3: Cài đặt và ứng dụng: trong chương này em trình bày về cài đặt mô hình tri thức mờ, thực nghiệm trên bộ dữ liệu UCI, đánh giá mô hình đồ thị tri thức mờ. Kết luận: đánh giá những công việc đã thực hiện được và chưa thực hiện được trong quá trình làm luận văn, đề xuất hướng phát triển trong tương lai. Lý thuyết đồ thị Đồ thị được xây dựng dựa trên các đỉnh (hay nút), các cung (cạnh) là đường nối giữa các đỉnh của đồ thị với nhau. Khi lập trình để biểu diễn trên máy tính người ta có thể sử dụng nhiều cách khác nhau.
Trong các lĩnh vực sử dụng đồ thị nhiều như: Toán học, tin học, … Khi đó đồ thị là một phương pháp tỏ ra hiệu quả với các bài toán ứng dụng trong thực tế. Đồ thị giải quyết được các bài toán thực tế như: giao thông, du lịch, giáo dục,… Nó là một công cụ trực quan hóa để biểu diễn, diễn tả các bài toán. Một đồ thị được xây dựng có cấu trúc rời rạc, nó gồm 2 thành phần: tập các đỉnh và tập các cạnh. Khi đó đồ thị: G=(V,E) Trong đó đồ thị được gọi là G, tập các đỉnh được gọi là V, tập các cạnh được gọi là E.
Mỗi cạnh đồ thị cặp (u,v) với đỉnh u được nối với đỉnh v, hai đỉnh u, v thuộc vào tập V. Người ta chia đồ thị dựa trên tính chất của các cạnh trong tập E: - Đồ thị G là đơn đồ thị nếu như giữa hai đỉnh (u,v) của V chỉ có không quá một cạnh trong E để nối từ u tới v. - Đồ thị G là đồ thị đa cạnh nếu giữa đỉnh u và đỉnh v của V có thể có từ hai cạnh trong E nối từ đỉnh u tới đỉnh v. - Đồ thị G được gọi là đồ thị vô hướng (undirected graph) khi các cạnh nối giữa đỉnh u và đỉnh v trong đồ thị không định hướng.
- Đồ thị có hướng G (directed graph) là đồ thị các cạnh nối giữa đỉnh v với đỉnh u có định hướng, nó xác định chiều của đường đi của các cạnh trong đồ thị. Cạnh còn được gọi là cung trên đồ thị có hướng. Nếu cạnh nối đỉnh u với đỉnh v trong đồ thị tương ứng với 2 cung là: (u→v), (v→u). Khi đó đồ thị vô hướng cũng có thể coi là đồ thị có hướng.
Logic mờ Logic mờ xây dựng dựa trên lý thuyết mờ được sử dụng để suy luận, lập luận dựa trên việc xấp xỉ thay vì lập luận chính xác của logic (như lập luận tiến, lập luận lùi). Logic mờ được sử dụng như là một mặt ứng dụng của lý thuyết mờ để xử lý các giá trị mờ trong thế giới thực trong các bài toán thực tế. [1,2,3,4] Độ chính xác thường hay nhầm lẫn với xác suất. Nhưng, hai khái niệm này là hoàn toàn khác nhau, độ chính xác trong logic mờ không phải khả năng xảy ra một biến cố hay điều kiện nào đó mà là việc biểu diễn độ liên thuộc với các tập được định nghĩa không rõ ràng.
Logic mờ được xây dựng dựa trên độ thuộc có miền giá trị trong đoạn [0,1], nó biểu diễn các câu không chính xác trong thế giới thực như: “hơi nhanh”, “rất nhanh”, “hơi chậm”, “rất chậm”, “chậm một chút”…. Khi đó, các phép toán trong tập hợp có thể không xác định được đầy đủ các quan hệ giữa các câu này với nhau. Do vậy, sự quan hệ giữa lý thuyết xác suất và logic mờ có liên quan tới nhau. Ý tưởng về Logic mờ được giáo sư Lotfi Zadeh của Đại học California- Berkeley xây dựng từ những năm 1965.
Tuy được ứng dụng thành công trong nhiều lĩnh vực, nhưng nó cũng tồn tại nhiều nhược điểm khác nhau trên nền tảng toán học, dẫn đến một số nghiên cứu khoa học về logic mờ không chỉ rõ được luận cứ vững chắc mà chỉ thực hiện thông qua thực nghiệm của thế giới thực. Nó bị phủ nhận bởi một số kỹ sư ngành điều khiển tự động vì khả năng thẩm định và một số lý do khác. Trong toán học người ta luôn mong muốn xây dựng một nền tảng vững chắc trong mọi nền tảng, nhưng thực tế có một số hiện tượng, sự vật chỉ đúng và sai trong từng hoàn cảnh, thời điểm khác nhau khi đó các mô hình toán học biểu diễn không đầy đủ và toàn vẹ được. Ví dụ trong lĩnh vực thống kê, các nhà thống kê luôn khẳng định rằng chỉ có xác suất thể hiện cho các sự không chắc chắn cho sự chặt chẽ của toán học trong một không gian vô hạn, nhưng thực tế thì mọi thứ đều có giới hạn, khi đó xác 11 suất thống kê không chỉ ra được sự chặt chẽ đó.
Một số nhà khoa học còn phê phán về việc xác định giá trị của hàm thuộc trong logic mờ được xây dựng chưa đầy đủ và thiếu sự chặt chẽ về nền tảng toán học so với các lý thuyết toán học. Giới thiệu tập mờ (Fuzzy set) Tập mờ [5,6,7] được xây dựng dựa trên lý thuyết mờ. Khi đó, mỗi tập mờ xây dựng trên một tập nền X, mỗi giá trị x của tập nền X được xác định bởi một giá trị hàm thuộc . Do vậy, một tập mờ A được xác định dựa trên cặp (x, ) như sau: A x, x | x X , 0,1 (1.1) Trong đó : (x) gọi là hàm thuộc của giá trị x của tập mờ A.
Khi đó, được xác định thông qua một hàm để ánh xạ giá trị của tập nền X với các giá trị của hàm thuộc. Ánh xạ được xác định từ 1 phần tử x trong tập nền X tới giá trị hàm thuộc được xác định giá trị trong đoạn [0,1]. 1: Hàm thuộc cơ bản trong logic mờ 12 Khi đó, một tập mờ được xây dựng dựa trên hai yếu tố cơ bản là: không gian nền và hàm thuộc. Mỗi hàm thuộc được xây dựng dựa trên ý nghĩa của từng bài toán, vấn đề trong thực tế cho phù hợp.
Người ta, có thể lựa chọn một số hàm thuộc cơ bản hoặc hàm thuộc được định nghĩa mới. Tuy nhiên, các hàm thuộc phản ảnh ý nghĩa thực tiễn của bài toán đề ra. Hàm thuộc khi xây dựng dựa trên tập nền của bài toán, vấn đề ngữ nghĩa để xác định việc ảnh hưởng đến phân phối giá trị của biến ngữ nghĩa. Một số hàm thuộc cơ bản như sau : hàm phân bố xác suất, hàm lượng giác (hàm sin, hàm cosin,…), hàm phân phối chuẩn, ….
(thể hiện trong hình 1. Để lựa chọn hàm thuộc phù hợp, người ta lựa chọn hàm thuộc phù hợp dựa trên bài toán thực tế. Ngoài các hàm thuộc cơ bản đã có, trong một số ngôn ngữ cũng hỗ trợ một số hàm thuộc có sẵn. Trong Matlab cũng xây dựng một số hàm thuộc trong thư viện Fuzzy.
Các yếu tố cơ bản khi lựa chọn hàm thuộc: phân tích thống kê dữ liệu, hiểu ý nghĩa dữ liệu. Tuy nhiên, người dùng có thể xây dựng hàm thuộc phù hợp với bài toán, đảm bảo giá trị của hàm thuộc luôn thuộc trong [0,1]. Ví dụ có thể xây dựng hàm thuộc như sau : x X A xi Nếu X là tập hợp các đối tượng rời rạc i A (1.2) A x / x Nếu X là không gian liên tục X Các phép toán trên tập mờ Dựa trên lý thuyết mờ, các pháp toán cơ bản của tập mờ được xây dựng dựa trên tập nền và hàm thuộc. Những phép toán cơ bản của tập mờ cũng là các phép toán cơ bản của tập hợp như: phép giao, phép hợp, phép phủ định.
Phép giao: giao giữa 2 tập mờ: A và B trên cùng một tập nền X, được xác định dựa trên một ánh xạ của 2 tập hợp thông qua giá trị của hàm thuộc được xác định bởi công thức (1.3) Khi đó, một tiêu chuẩn T được xác định cho điểm giao nhau của phép toán mờ, tiêu chuẩn T thỏa mãn các yêu cầu về một toán hạng chuẩn. 13 Toán hạng chuẩn T xác định là ánh xạ T() thoả mãn các điều kiện sau: Điểm biên: T(e, 1) = T(1, e) = e ; T(0, 0) = 0 (1.4) Đơn điệu: T(e, f) T(m, n) nếu e m và f n (1.7) Mỗi điều kiện khác nhau dẫn đến tác động khác nhau của tập mờ. Khi đó ý nghĩa của các điều kiện như sau : - Điểm biên tác động vùng danh giới và giới hạn của tập mờ. - Đơn điệu tác động đến tính liên thuộc của các giá trị mờ.
- Giao hoán chỉ ra các giá trị mờ không ảnh hưởng đến thứ tự của chúng khi xuất hiện. - Kết hợp chỉ ra sự kết hợp giữa các phần tử theo từng cặp. Dựa trên cơ sở đó, một số phép toán giao thoả mãn chuẩn T-norm thường được sử dụng như sau: Min T(e,f)= min(e,f) (1.9) Chuẩn max : T(e,f)=max{e+f-1,0} (1.12) 0 max(x, y) 1 Phép hợp : Giống như giao điểm mờ, phép hợp dựa trên sự kết hợp mờ với ánh xạ nhị phân xác định trên S.13) Những giá trị của phép hợp mờ thường được xác định là những phép toán dựa trên các tiêu chuẩn của phép giao, thỏa mãn các tiêu chuẩn cơ bản trong tiêu chuẩn S. 14 Tiêu chuẩn S là ánh xạ của phép toán 2 ngôi S() thoả mãn: Điểm biên: S( e, 0) = S(0, e) = e ; S(1, 1) = 1; (1.14) Đơn điệu: S( e, f) S(m, n) nếu e m và f n (1.17) Từ đó, Zadeh xậy dựng các phép toán dựa trên tiêu chuẩn S cho phép toán giao, cụ thể như sau: Phép max S(e,f)= max(e,f) (1.19) Chuẩn min T(e,f)=min{e+f,1} (1.20) max(x, y) x y 1 S(x, y) 1 x y 1 Chuẩn max (1.22) 1 min(x, y) 0 Phép phủ định : là một phép toán cơ bản của logic.
Được sử dụng để suy rộng các toán tử. Phép phủ định thỏa mãn điều kiện như sau: Hàm G: [0,1][0,1] được gọi là hàm phủ định nếu điều kiện sau đây được thoả mãn: Điều kiện biên: G(0)=1 và G(1)=0 Đơn điệu: G(A) G(B) nếu A B Nếu G(G(A)) = A thì phép phủ định này gọi là phủ định chặt. Trên cơ sở đó, người ta thường sử dụng một số phép toán phủ định như sau: Zadeh: G(x)=1-x Sugeno: Gp(x)=(1-x)/(x*p) (1.