Luận án Nghiên cứu ngữ nghĩa tính toán của từ ngôn ngữ và ứng dụng vào việc xây dựng hệ mờ tối ưu dựa trên luật

LỜI CAM ĐOAN. i

LỜI CẢM ƠN . ii

MỤC LỤC .iii

DANH MỤC CÁC BẢNG BIỂU .viii

DANH MỤC CÁC HÌNH VẼ. x

MỞ ĐẦU. 1

CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ . 9

1.1. Một số kiến thức cơ bản về lý thuyết tập mờ . 9

1.1.1. Định nghĩa tập mờ. 9

1.1.2. Xây dựng hàm thuộc. 10

1.1.3. Biến ngôn ngữ . 10

1.1.4. Phân hoạch mờ. 11

1.2. Một số kiến thức về đại số gia tử . 12

1.2.1. Khái niệm đại số gia tử . 13

1.2.2. Một số tính chất của đại số gia tử tuyến tính . 14

1.2.3. Độ đo tính mờ của các giá trị ngôn ngữ . 14

1.2.4. Định lượng ngữ nghĩa của giá trị ngôn ngữ . 16

1.2.5. Khoảng tính mờ . 18

1.2.6. Hệ khoảng tương tự. 19

1.3. Hệ mờ dựa trên luật. 20

1.3.1. Các thành phần của hệ mờ . 20

1.3.2. Các mục tiêu khi xây dựng FRBS . 23

pdf131 trang | Chia sẻ: mimhthuy20 | Ngày: 19/09/2020 | Lượt xem: 68 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Luận án Nghiên cứu ngữ nghĩa tính toán của từ ngôn ngữ và ứng dụng vào việc xây dựng hệ mờ tối ưu dựa trên luật, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ữ liệu p = (dp1, dp2, , dpn, dp(n+1)) D, sinh luật ngôn ngữ rp có dạng (2.6); Chọn số l ngẫu nhiên trong đoạn [1, lmax]; r  rp; Sinh l số nguyên {i1,, il}ngẫu nhiên thỏa mãn 1 ≤ i1 < < il ≤ n; for i 1 to n do if i {i1,, il} then r[i]  “Don’tcare”;//Đặt tiền điều kiện thứ i của r bằng “Don’tcare” endif endfor return r; End; Hàm sinh luật ngôn ngữ từ mẫu dữ liệu này sẽ được sử dụng để sinh luật ngôn ngữ trong thuật toán này và các thuật toán ở phần sau của luận án. Với phương pháp sinh luật này sẽ làm giảm không gian tìm kiếm các luật phải xem xét rất nhiều so với sinh luật bằng tổ hợp tất cả các tập mờ sử dụng 53 cho các biến. Thật vậy, chúng ta xem xét một ví dụ minh họa sau đây. Với tập dữ liệu PT được cho trong bảng 2.10, số thuộc tính n = 26 và số mẫu dữ liệu là 15,000. Trong [10] Alcalá và các cộng sự sử dụng T = 3 tập mờ cho mỗi biến. Khi đó số luật khởi tạo có độ dài n được sinh ra bằng tổ hợp các từ của tất cả các biến là 327. Giả sử độ dài của các luật trong hệ luật cần xây dựng  5. Khi đó một luật có độ dài n sẽ sinh ra ∑ 𝐶26 𝑙5 𝑙=1 = 83,681 luật có độ dài  5. Như vậy, tổng số tất cả các luật phải xem xét của phương pháp này cho tập dữ liệu PT là 327  83,681 = 638,117,623,141,197,000  6.38E17. Với phương pháp dựa trên ĐSGT, mỗi mẫu dữ liệu chỉ sinh ra duy nhất một luật ngôn ngữ có độ dài n theo thuật toán GenerateRule. Khi đó tổng số lượng các luật có độ dài  5 phải xem xét là 15,000  83,618 = 1,255,215,000 = 1.26E09. Số luật này thì nhỏ hơn khoảng 5.0E8 lần số luật phải xem xét trong các phương pháp tiếp cận dựa trên lý thuyết tập mờ. Như vậy không gian luật phải xem xét của các phương pháp tiếp cận dựa trên ĐSGT giảm đi đáng kể so với phương pháp tiếp cận dựa trên lý thuyết tập mờ. Ví dụ minh họa phương pháp sinh luật của thuật toán GenerateRule: Cho tập dữ liệu mẫu của bài toán dự báo tiêu hao nhiện liệu của ô tô (Auto MPG6). Mỗi mẫu dữ liệu gồm 5 biến đầu vào (n = 5), biến 𝔛1 là khoảng cách di chuyển, 𝔛2 là số sức ngựa, 𝔛 3 là trọng lượng xe, 𝔛4 sự tăng tốc, 𝔛5 là năm sản xuất, và một biến đầu ra 𝔛 6 là số dặm đi được trên một galon xăng. Các mẫu dữ liệu của tập dữ liệu được chuẩn hóa về đoạn [0, 1]. Phương pháp sinh các luật có chiều dài tối đa lmax từ mẫu dữ liệu p = {dp1, dp2, dp3, dp4, dp5, dp6} = {0.0594, 0.1304, 0.0970, 0.7440, 0.0833, 0.4521} bằng thuật toán GenerateRule được mô tả như sau. Ký hiệu AX1, AX2, AX3, AX4, AX5 là ĐSGT cho các biến đầu vào và AX6 là ĐSGT cho biến đầu ra. Các ĐSGT này đều có cấu trúc như sau: phần từ sinh {c-, c+}, hai gia tử H = {L, V}, phần tử trung hòa w. Các tham số tính mờ có giá trị: µLj = 𝜇𝐶𝑗 − = 0.5 và chiều dài tối đa của các hạng từ kj = 2. Với các tham số đã cho ta có tập các từ sử dụng cho mỗi biến Xj(kj) = {0, Vc -, c-, Lc-, w, Lc+, c+, Vc+, 1} và từ Don'tCare được viết tắt là DC. Hệ khoảng tương tự của các từ trong tập Xj(kj), j)S k( = {⁡ℭ(0) = [0, 0.0625], ℭ(Vc -) = [0.0625, 0.1875], ℭ(c-) = 54 [0.1875, 0.3125], ℭ(Lc-) = [0.3125, 0.4375], ℭ(w) = [0.4375, 0.5625], ℭ(Lc+) = [0.5625, 0.6875], ℭ(c+) = [0.6875, 0.8125], ℭ(Vc+) = [0.8125, 0.9375], ℭ(1) = [0.9375, 1]}. Với mẫu dữ liệu đã p = {dp1, dp2, dp3, dp4, dp5, dp6} = {0.0594, 0.1304, 0.0970, 0.7440, 0.0833, 0.4521}, giả sử cần sinh các luật có độ dài tối đa lmax = 4 (lmax là giá trị do người dùng chọn tùy thuộc vào bài toán cụ thể, nó thường nhỏ hơn n để tạo ra các luật có độ dài ngắn nhằm làm tăng tính dễ hiểu của luật). . Xét mẫu dự liệu p, ta có dp1  ℭ(0), dp2 ⁡ℭ(Vc-), dp3 ⁡ℭ(Vc-), dp4 ⁡ℭ(c+), dp5 ⁡ℭ(Vc-), dp6⁡ℭ(w). Như vậy từ mẫu dữ liệu p ta sinh được luật rp có độ dài n như sau: rp: If 𝔛1 is 0 and 𝔛2 is Vc- and 𝔛3 is Vc- and 𝔛4 is c+ and 𝔛5 is Vc- then 𝔛6 is w Từ luật rp sinh luật r có độ dài l  lmax = 4, giả sử với l = 3, chọn 3 số ngẫu nhiên khác nhau trong đoạn [1, n], giả sử là {1, 2, 5}, khi đó luẩt r chỉ bảo gồm các điều kiện tiền đề tương ứng với biến {𝔛1 𝔛2, 𝔛5} của luật rp, các điều kiện tiền đề tương ứng với biến {𝔛2, 𝔛4} là DC. r: If 𝔛1 is 0 and 𝔛2 is Vc- and 𝔛3 is DC and 𝔛4 is DC and 𝔛5 is Vc- then 𝔛6 is w Giả sử l = 2 và các số {1, 4} thì khi đó ta có luật r là: r: If 𝔛1 is 0 and 𝔛2 is DC and 𝔛3 is DC and 𝔛4 is c+ and 𝔛5 is DC then 𝔛6 is w 3) Phát triển thuật toán tiến hóa a. Mã hóa cá thể Theo giả thiết mỗi biến 𝔛j của một tập dữ liệu đã cho chỉ có một gia tử dương Vj (Very), một gia tử âm Lj (Little) và mục tiêu cần tối ưu là tham số tập mờ, số từ ngôn ngữ và cơ sở luật. Do đó mỗi cá thể của quần thể được mã hóa gồm ba phần (Cµ, Ck, CRB) xem hình 2.3, trong đó: - Cµ: Biểu diễn các tham số tính mờ của các ĐSGT tương ứng với các biến. Nó là một véc tơ  = (1,,n+1), trong đó j = {Lj, 𝐶𝑗 −} với j = 1,..,n+1. Như vậy nó sẽ có 2(n+1) gen các số thực. - Ck: Biểu diễn các giá trị xác định độ dài tối đa của các từ ngôn ngữ được 55 sinh ra từ ĐSGT AXj, gồm n+1 số tự nhiên kj. - CRB: Biểu diễn cơ sở luật của LRBS gồm M luật, mỗi luật là một véc tơ có n+1 phần tử là các từ ngôn ngữ. Như vậy CRB sẽ có M(n+1) gen là các từ ngôn ngữ. Hình 2.3. Cấu trúc mã hóa một cá thể Để giảm không gian tìm kiếm và hệ luật sinh ra đạt được tính giải nghĩa cao, ta giới hạn số luật của mỗi cơ sở luật nằm trong khoảng [Mmin, Mmax]. Gắn với mỗi cá thể là một véc tơ hàm mục tiêu gồm hai thành phần (MSE, Comp), trong đó MSE được xác định theo (1.12) và Comp là tổng độ dài của các luật trong cơ sở luật được xác định theo công thức (1.13) biểu thị tính giải nghĩa được của hệ luật dựa trên độ phức tạp ở mức cơ sở luật. b. Các toán tử di truyền - Toán tử lai ghép Với hai cá thể bố mẹ p1, p2 sử dụng phương pháp lai ghép một điểm (one- point crossover) độc lập trên Cµ, Ck và CRB. Trên Cµ, điểm lai ghép được chọn ngẫu nhiên trong đoạn [1, 2(n+1) - 1]. Trên Ck, điểm lại ghép được chọn ngẫu nhiên trong đoạn [1, n+1]. Trên CRB, điểm lai ghép được chọn ngẫu nhiên trong đoạn [1, min-1], trong đó min là số luật ít nhất của 2 cơ sở luật trong p1 và p2. Lưu ý: Nếu trên CRB toán tử lai ghép không được thực hiện thì đột biến luôn xảy ra trên nó. - Toán tử đột biến Với cá thể con p thực hiện đột biến theo thứ tự và độc lập trên Cµ, Ck và CRB. Trên Cµ: Lựa chọn ngẫu nhiên một số nguyên trong [1, 2(n + 1)], thực hiện thay thế gen tại vị trí được chọn bằng một giá trị được chọn ngẫu nhiên trong đoạn [µmin, µmax], nếu gen được chọn biểu diễn giá trị µLj, hoặc một giá trị ngẫu nhiên trong đoạn [fmmin, fmmax], nếu gen được chọn biểu diễn giá trị của 𝐶𝑗 − . Các khoảng này được ràng buộc trước bởi người dùng để bảo toàn ngữ 56 nghĩa của các gia tử và các phần tử sinh. Trên Ck: Nếu đột biến xảy ra thì chọn ngẫu nhiên một gen thứ f[1, (n+1)], thay đổi giá trị của gen này bằng cách ngẫu nhiên tăng hoặc giảm một đơn vị. Nếu giá trị mới nằm ngoài đoạn [1, kmax] thì đột biến sẽ bị bỏ qua. Trên CRB: Chúng ta áp dụng một trong hai toán tử sau đây trên mỗi cá thể, tức là nếu áp dụng toán từ thứ nhất thì không áp dụng toán tử thứ hai và ngược lại. 1) Toán tử 𝔬m1 thay đổi các giá trị tại  gen của CRB: Lựa chọn ngẫu nhiên một số nguyên  trong đoạn [1, max], trong đó max được xác định trước, và sau đó, chọn ngẫu nhiên  gen của CRB. Thay đổi giá trị tại mỗi gen được chọn bằng một giá trị ngẫu nhiên hoặc là trong X(kj)  {‘Don’tcare’}, nếu gen tương ứng với biến j  n + 1, hoặc trong X(kj), nếu gen tương ứng với biến j = n + 1. 2) Toán tử 𝔬m2 bổ sung  luật vào RB hiện tại có M luật được biểu diễn bởi CRB: Chọn ngẫu nhiên một số nguyên  trong [1, max], trong đó max được xác định trước, nếu M +  > Mmax thì bổ sung ’ = min{, Mmax – M} luật được sinh ra từ ’ mẫu dữ liệu được chọn ngẫu nhiên từ tập dữ liệu đã cho vào RB hiện tại, bằng cách sử dụng hàm GenerateRule. Chú ý: - Trong quá trình tiến hóa, nếu một luật trở nên có độ dài bằng 0, tức là phần tiền đề của nó đều là “Don’tcare”, nó sẽ được loại bỏ. Và nếu một số luật trùng nhau thì chỉ giữ lại một luật. - Sau khi lai ghép hoặc đột biến, RB trong CRB có thể có những luật mà phần tiền đề của nó có những tiền điều kiện là những từ ngôn ngữ không nằm trong tập các từ ngôn ngữ sử dụng cho biến tương ứng (tức là các từ có độ dài lớn hơn kj) khi đó chúng ta phải thực hiện chuẩn hóa các luật. c. Chuẩn hóa cơ sở luật Định nghĩa 2.1: [iii] Luật rq được gọi là luật không chuẩn nếu j sao cho từ Aq,j là điều kiện tiền đề tương ứng với biến 𝔛j có độ dài lớn hơn kj. 57 Sau khi thực hiện lai ghép trên CRB hoặc đột biến trên Ck có thể tạo ra các cá thể con chứa các luật không chuẩn. Các luật này cần phải được chuẩn hóa nhưng không bị mất đi ngữ nghĩa lõi của nó. Để làm được việc này, chúng ta phải dựa trên nguyên tắc sinh từ ngôn ngữ của ĐSGT. Các từ được sinh ra từ ĐSGT đều có dạng hk-1hk-2..h1c, trong đó các hi (i = 1,..,k-1) là các gia tử và c là phân tử sinh. Khi đó nếu ta bỏ bớt các gia tử ở bên trái của từ thì ngữ nghĩa của từ mới trở nên khái quát hơn nhưng nó vẫn giữ được ngữ nghĩa lõi của từ gốc. Vì vậy, việc chuẩn hóa được thực hiện như sau: xét từng luật của cơ sở luật, nếu luật rq không chuẩn do điều kiện tiền đề hoặc kết luận jqA , gây nên thì loại bỏ các gia tử bên trái của từ jq A , để được từ ' , jq A có độ dài đúng bằng kj. Ví dụ: Giả sử cá thể cha mẹ p có p.Ck = {1, 3, 3}, và có luật rq trong cơ sở luật c.CRB như sau: rq: 𝔛1 is c+ and 𝔛2 is VVc- then 𝔛3 is Lc+ Sau khi lại ghép trên phần Ck tạo ra cá thể con c có c.Ck = {2, 1, 1} và luật rq là một luật trong c.CRB. Ta thấy rq là luật không chuẩn do tiền điều kiện tương ứng với biến 𝔛1 là VVc- có độ dài 3 trong khi tập từ sử dụng cho biến này hiện tại có độ dài tối đa là 1 và do kết luận 𝔛3 là Lc+ có độ dài 2 trong khi tập từ sử dụng cho kết luận hiện tại có độ dài tối đa là 1. Vì vậy, luật rq cần phải được chuẩn hóa bằng cách loại bỏ 2 gia tử VV của VVc- để được từ c- có độ dài 1, và gia tử L của Lc+ để được từ c+ có độ dài 1. Khi đó ta được luật rq chuẩn trong cơ sở luật c.CRB như sau: rq: 𝔛1 is c+ and 𝔛2 is c- then 𝔛3 is c+ d. Thuật toán tiến hóa đa mục tiêu Tương tự như trong Acalá [8-10], Antonelli [12-15], chúng tôi áp dụng lược đồ tiến hóa (2+2)M-PAES được đề xuất bởi Cococcioni và các cộng sự trong [16] là một lược đồ cải tiến của lược đồ tiến hóa (2+2)PAES của Knowles và Corne trong [36]. Quá trình tiến hóa được thực hiện theo mô tả sau đây: Đầu tiên thuật toán sinh ra hai cá thể (hay là lời giải) 𝖎1, 𝖎2 có dạng như biểu diễn trong hình 2.3. Đối với phần Cµ của mỗi cá thể 𝖎k, k = 1, 2, các gen tương ứng với µLj và (μ𝐶𝑗 −) được sinh ra ngẫu nhiên từ các đoạn con xác định 58 trước [µmin, µmax] và [fmmin, fmmax] của đoạn [0, 1] tương ứng. Đối với phần Ck, các gen là các số nguyên được chọn ngẫu nhiên trong đoạn [1, kmax]. Đối với phần CRB, nó bao gồm Mk luật ngôn ngữ, Mk là một số nguyên được chọn ngẫu nhiên từ khoảng [Mmin, Mmax] được xác định trước và sau đó Mk luật ngôn ngữ của nó được sinh bởi hàm GenerateRule từ các mẫu dữ liệu được chọn ngẫu nhiên. Hai cá thể con 𝖎1, 𝖎2 được lưu vào mặt Pareto. Trong mỗi thế hệ, hai cá thể cha mẹ 𝔭1 và 𝔭2 được chọn ngẫu nhiên từ mặt Pareto được lưu trữ để tạo ra hai cá thể con 𝔬 1, 𝔬 2 bằng việc áp dụng toán tử lai ghép và đột biến được mô tả trong mục b. Trước tiên thuật toán áp dụng các toán tử lai ghép độc lập trên mỗi phần Cµ, Ck, CRB của 𝔭1 và 𝔭2 với xác xuất tương ứng 𝑃𝐶𝜇, 𝑃𝐶𝑘 và 𝑃𝐶𝑅𝐵 để tạo ra hai cá thể con 𝔬1 và 𝔬2. Sau đó lần lượt áp dụng các toán tử đột biến trên từng cá thể con. Với mỗi cá thể con 𝔬k (k =1, 2), thực hiện các toán tử đột biến lần lượt trên Cµ, Ck và CRB với xác suất tương ứng là 𝑃𝑚𝜇 , 𝑃𝑚𝑘và 𝑃𝑚𝑅𝐵 . Lưu ý: nếu toán tử lai ghép trên phần CRB không được thực hiện thì toán tử đột biến phải được thực hiện trên thành phần này. Ngoài ra, chúng ta phải thực hiện toán tử đột biến trên Cµ và Ck trước khi thực hiện toán tử đột biến trên CRB. Vì khi thực hiện toán tử đột biến thêm luật trên CRB cần sử dụng những giá trị mới nhất trên phần Cµ và Ck để sinh luật. Mỗi cá thể con 𝔬1 và 𝔬2 trở thành một lời giải ứng cử, nếu nó không bị trội bởi bất kỳ lời giải nào đang được lưu trữ trong mặt Pareto. Khi đó, nó được đưa vào lưu trữ trong mặt Pareto và đồng thời những lời giải đang được lưu trữ trong mặt Pareto bị trội bởi lời giải này sẽ bị loại bỏ. Số cá thể được lưu trữ tối đa trong mặt Pareto thường được cố định và được xem như là tham số được người dùng xác định trước. Khi mặt Pareto lưu trữ đầy, và nếu một lời giải ứng cử được bổ sung vào thì một lời giải (có là lời giải ứng cử) thuộc về vùng có mật độ cao nhất bị loại bỏ. Vùng có mật độ cao nhất được xác định theo thuật toán của Knowles và Corne trong [36]. Nếu vùng có mật độ cao nhất có nhiều hơn một lời giải, thì chọn ngẫu nhiên một lời giải trong chúng để loại bỏ. Chúng ta ký hiệu 𝔓 là quần thể hiện tại (mặt xấp xỉ tối ưu Pareto). Các bước cơ bản của thuật toán được mô tả như sau. Algorithm HA-PAES-SG 59 Input: - Tập mẫu dữ liệu: D = {(pi, yi), i = 1, 2,..., N}, - Cận dưới, cận trên độ đo tính mờ của gia tử L: µmin, µmax - Cận dưới, cận trên độ đo tính mờ của phần tử sinh c+: fmmin, fmmax - Giới hạn độ dài tối đa của các hạng từ: kmax - Số gen tối đa có thể đột biến khi đột biến xảy ra trên CRB: max - Số luật tối đa có thể thêm vào RB khi đột biến thêm luật xảy ra: max - Số luật tối thiểu, số luật tối đa của cơ sở luật: Mmin, Mmax - Độ dài tối đa của luật: lmax - Số cá thể tối đa có thể lưu trữ trong mặt Pareto: archiveSize - Số thế hệ tối đa của quá trình tiến hóa: G - Xác suất xảy ra lai ghép trên Cµ: 𝑃𝐶𝜇 - Xác suất xảy ra lai ghép trên Ck: 𝑃𝐶𝑘 - Xác suất xảy ra lai ghép trên CRB: 𝑃𝐶𝑅𝐵 - Xác suất xảy ra đột biến trên Cµ: 𝑃𝑚𝜇 - Xác suất xảy ra đột biến trên Ck: 𝑃𝑚𝑘 - Xác xuất tăng giá trị k khi xảy ra đột biến trên Ck: 𝑃𝑖𝑛𝑐_𝑘 - Xác suất xảy ra đột biến trên CRB: 𝑃𝑚𝑅𝐵 - Xác suất xảy ra đột biến thêm luật trên CRB: 𝑃𝐴𝑑𝑑 Output: - Mặt xấp xỉ tối ưu Pareto: 𝔓 Begin Sinh ngẫu nhiên 2 cá thể 𝔦1, 𝔦2; Tính các mục tiêu MSE, Comp của i1, 𝔦2; testAdd (𝔦1,𝔓 , archiveSize); //Bổ sung 𝔦1 vào 𝔓 testAdd (𝔦1,𝔓 , archiveSize); //Bổ sung 𝔦2 vào 𝔓 nếu⁡có⁡thể for i  1 to G do Chọn ngẫu nhiên hai cá thể bố mẹ 𝔭1, 𝔭2 trong 𝔓; //𝔭1, 𝔭2 có thể trùng nhau) [𝔬1, 𝔬2]  crossover (𝔭1, 𝔭2); //Thực hiện lai ghép hai cá thể 𝔭1, 𝔭2 để 60 sinh ra hai cá thể con 𝔬1, 𝔬2 mutation (𝔬1); //Đột biến trên 𝔬1 mutation (𝔬2); // Đột biến trên 𝔬2 Chuẩn hóa cơ sở luật của 𝔬1, 𝔬2 theo thuật toán trong mục c; Tính giá trị mục tiêu MSE, Comp của 𝔬1, 𝔬2; testAdd (𝔬1,𝔓 , archiveSize); //Bổ sung 𝔬1 vào 𝔓 nếu có thể testAdd (𝔬2,𝔓 , archiveSize); //Bổ sung 𝔬2 vào 𝔓 nếu có thể endfor return 𝔓; End Cá thể con 𝔬 nếu không bị trội bởi bất kỳ cá thể nào trong 𝔓 thì 𝔬 được bổ sung vào 𝔓, đồng thời loại bỏ tất cả những cá thể trong 𝔓 bị trội bởi 𝔬. Nếu số cá thể trong 𝔓 lớn hơn số lượng tối đa được phép lưu trữ trong 𝔓 thì loại bỏ ngẫu nhiên một cá thể trong vùng có mật độ cao nhất ra khỏi 𝔓, vùng có mật độ cao nhất được xác định theo thuật toán trong [36]. Hàm testAdd kiểm tra và bổ sung cá thể 𝔬 vào mặt Pareto 𝔓 nếu có thể. Hàm trả lại giá trị true nếu 𝔬 được thêm vào 𝔓 và trả lại false nếu 𝔬 không được thêm vào 𝔓. Algorithm testAdd (𝔬, 𝔓, archiveSize) Input: - Mặt xấp xỉ tối ưu Pareto: 𝔓 - Cá thể con được xem xét thêm vào mặt Pareto𝔓: 𝔬 - Số cá thể tối đa được phép lưu trữ trong Pareto𝔓: archiveSize Output: true/false Begin if 𝔬 không bị trội bởi bất kỳ cá thể nào của 𝔓 then Bổ sung 𝔬 vào 𝔓; for each 𝔵 in 𝔓 do if 𝔬 trội hơn 𝔵 then Loại bỏ 𝔵 ra khỏi 𝔓; endif 61 if |𝔓 | > archiveSize then Loại bỏ 1 cá thể trong vùng có mật độ cao nhất ra khỏi 𝔓; return true; endfor endif else return false; End 4) Kết quả thử nghiệm Chúng tôi tiến hành thử nghiệm thuật toán HA-PAES-SG tương tự phương pháp thử nghiệm trong [14] trên 6 tập dữ liệu hồi quy cho trong bảng 2.7 được lấy tại địa chỉ các tập mẫu dữ liệu đã được chuẩn hóa về đoạn [0, 1] và các tham số của thuật toán cho trong bảng 2.8. Phương pháp thử nghiệm kiểm tra chéo Five-Fold, mỗi tập dữ liệu được chia thành 5 phần (4 phần dùng để huấn luyện, 1 phần dùng để kiểm tra). Mỗi Fold thử nghiệm 6 lần, như vậy tổng số lần thử nghiệm là 6 x 5 = 30 lần. Mỗi lần thử nghiệm tạo ra một mặt Pareto xấp xỉ tối ưu tương ứng, sắp xếp các cá thể trong mặt Pareto theo thứ tự tăng dần của giá trị MSE trên tập huấn luyện. Trên mỗi mặt Pareto đã được sắp chỉ giữ lại số cá thể bằng số cá thể của mặt Pareto có ít cá thể nhất trong 30 mặt Pareto nhưng không quá 20 cá thể. Thực hiện tính các giá trị trung bình MSEtr và MSEts (MSE trên tập huấn luyện và tập kiểm tra), Comp (trung bình độ phức tạp), SDtr, SDts (độ lệch chuẩn của MSEtr và MSEts) trên 30 mặt Pareto. Như vậy với mỗi tập dữ liệu ta thu được một mặt Pareto xấp xỉ tối ưu trung bình theo hai mục tiêu giá trị MSE trên tập huấn luyện và Comp. Các mặt Pareto xấp xỉ tối ưu trung bình của 6 tập dữ liệu được thể hiện trong hình 2.4. Bên cạnh thể hiện trực quan mặt xấp xỉ tối ưu Pareto, chúng tôi thực hiện phân tích thống kê bằng phương pháp kiểm định giả thuyết t-test với độ tin cậy 95% trên giá trị MSEtr và MSEts để xác định có sự khác biệt thống kê giữa kết quả được tạo ra từ thuât toán của chúng tôi đề xuất và các thuật toán trong 14] hay không?. Ký hiệu MSEtr, MSEts, SDtr, SDts, ttr, tts lần lượt là giá trị MSE trung bình, độ lệch chuẩn, kết quả thống kê trên tập dữ liệu huấn luyện, tập dữ liệu kiểm 62 tra và Comp, #R lần lượt là trung bình độ phức tạp và trung bình số luật của hệ luật. Bảng 2.7 Các tập dữ liệu được sử dụng thử nghiệm trong [14] STT Tên tập dữ liệu Số mẫu Số thuộc tính 1 Electrical Maintenance 2 (ELE2) 1056 4 2 Weather Ankara (WA) 1609 9 3 Weather Izmir (WI) 1461 9 4 Treasury (TR) 1049 15 5 Stock (STP) 950 9 6 Auto-MPG 6 (MPG6) 398 5 Bảng 2.8 Các tham số thử nghiệm min = fmmin =0.3, max =fmmax = 0.7 PAdd = 0.75 Pinc_k = 0.5 𝑃𝐶𝜇 = 0.75, 𝑃𝐶𝑘 = 0.3, 𝑃𝐶𝑅𝐵 = 0.3 kmax = 3, lmax = 5, max = 5, max = 5 𝑃𝑚𝜇 = 0.3, 𝑃𝑚𝑘 = 0.3, 𝑃𝑚𝑅𝐵= 0.1 archiveSize = 64, MaxGen = 300,000 Mmin = 5, Mmax = 50 Tương tự như trong [14], chúng tôi áp dụng kiểm tra trên 3 điểm của mặt Pareto: điểm ứng với lời giải có MSEtr nhỏ nhất, Comp lớn nhất (kí hiệu là: FIRST), điểm ứng với lời giải có MSEtr, Comp trung bình (kí hiệu là: MEDIAN) và MSEtr lớn nhất, Comp nhỏ nhất (ký hiệu là: LAST). Các kết quả thống kê được trình bày trong các bảng 2.9 và A.1, A.2 trong phần phụ lục. Các ký hiệu được sử dụng tương tự như trong [14]: - “*” thể hiện dòng tương ứng có kết quả tốt nhất (với chữ in đậm) - “+” thể hiện dòng tương ứng có kết quả kém hơn kết quả tốt nhất “=” thể hiện không có sự khác biệt thống kê của dòng tương ứng với kết quả tốt nhất. Để giảm không gian trình bày của nội dung luận án, chúng tôi chỉ tổng hợp và phân tích các kết quả thử nghiệm tại điểm FIRST. Kết quả tổng hợp tại các điểm MEDIAN và LAST được trình bày chi tiết trong phần phụ lục. Chú ý, các giá trị được in đậm của các tiêu chí đối với một tập dữ liệu ngụ ý rằng 63 chúng thì tốt hơn những giá trị tương ứng. Bảng 2.9 So sánh kết quả thử nghiệm thuật toán HA-PAES-SG với các thuật toán (2+2)M-PAES(I) và (2+2)M-PAES(C) trong [14] tại điểm FIRST Tập dữ liệu Thuật toán #R Comp MSEtr SDtr ttr MSEts SDts tts ELE (2+2)M-PAES(I) 34.480 68.210 13660.200 1851.500 = 15768.600 3239.900 = (2+2)M-PAES(C) 24.240 96.480 13539.800 3764.700 * 15278.800 4129.000 = HA-PAES-SG 34.966 75.414 13732.337 2499.690 = 14969.681 4010.176 * WA (2+2)M-PAES(I) 20.200 75.160 1.911 0.381 + 1.997 0.298 + (2+2)M-PAES(C) 15.270 98.650 1.694 0.489 + 2.094 0.973 + HA-PAES-SG 24.100 58.000 1.265 0.175 * 1.383 0.229 * WI (2+2)M-PAES(I) 17.830 61.810 1.474 0.343 + 1.647 0.343 + (2+2)M-PAES(C) 13.120 83.550 1.441 0.276 + 1.556 0.243 + HA-PAES-SG 24.167 57.833 0.873 0.102 * 1.034 0.161 * MPG6 (2+2)M-PAES(I) 40.360 130.280 2.565 0.341 + 4.185 1.352 = (2+2)M-PAES(C) 48.030 121.660 2.820 0.428 + 4.304 1.365 = HA-PAES-SG 47.700 112.033 2.153 0.192 * 4.036 1.117 * STP (2+2)M-PAES(I) 48.530 184.000 0.748 0.098 + 0.934 0.175 = (2+2)M-PAES(C) 49.420 181.730 0.795 0.225 + 1.046 0.309 + HA-PAES-SG 49.100 146.700 0.567 0.109 * 0.720 0.192 * TR (2+2)M-PAES(I) 25.100 103.920 0.056 0.020 = 0.100 0.097 = (2+2)M-PAES(C) 19.100 147.000 0.066 0.025 = 0.132 0.132 = HA-PAES-SG 29.267 62.267 0.038 0.014 * 0.068 0.094 * Quan sát hình 2.4 chúng ta thấy rằng, thuật toán HA-PAES-SG tạo ra mặt xấp xỉ tối ưu Pareto trội hơn trên 5 tập dữ liệu, trừ ELE. Mặt Pareto trên tập kiểm tra không khác nhiều so với mặt Pareto trên tập huấn luyện trên 5 tập dữ liệu trừ MPG6. Từ đây chúng ta có thể kết luận rằng thuật toán tạo ra các LRBS có tính ổn định trong quá trình suy diễn. E L E 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 20 30 40 50 60 70 80 90 100 110 M SE x 104 Complexity Training 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 20 40 60 80 100 120 M SE x 104 Complexity Testing 64 W A W I M P G 6 S T P Hình 2.4. Mặt xấp xỉ tối ưu Pareto trung bình theo độ chính xác MSE và độ phức tạp Comp - Về mục tiêu độ chính xác: Từ bảng 2.9 cho thấy giá trị MSE của thuật toán HA-PAES-SG tốt hơn trên 5 tập dữ liệu trên cả tập huấn luyện và tập kiểm tra, ngoại trừ ELE thấp hơn trên tập huấn luyện. Tuy nhiên kết quả phân tích thống kê cho thấy thuật toán HA-PAES-SG và thuật toán tốt nhất không cho thấy sự khác biệt. Ở đây có sự khác biệt lớn về độ chính xác giữa thuật toán của chúng tôi với các thuật toán được so sánh. Như tập dữ liệu WA giá trị MSE của thuật toán của chúng tôi là 1.265 so với (1.911 và 1.694) trên tập dữ liệu huấn luyện và 1.383 so với (1.997 và 2.094) trên tập kiểm tra. Trên các tập dữ liệu WA, WI, STP và TR thuật toán của chúng tôi tạo ra các hệ luật có độ phức tạp thấp nhưng độ chính xác cao hơn nhiều như tập dữ liệu STR giá trị MSE là 0.9 1.1 1.3 1.5 1.7 1.9 2.1 2.3 2.5 20 30 40 50 60 70 80 90 100 M SE Complexity Training 0.9 1.1 1.3 1.5 1.7 1.9 2.1 2.3 2.5 20 30 40 50 60 70 80 90 100 M SE Complexity Testing 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 10 30 50 70 90 110 M SE x 104 Complexity Training HA-PAES-SG (2+2)M-PAES(C) (2+2)M-PAES(I) 0.8 1 1.2 1.4 1.6 1.8 2 2.2 10 30 50 70 90 M SE Complexity Testing 0.7 0.9 1.1 1.3 1.5 1.7 1.9 2.1 10 20 30 40 50 60 70 80 90 100 M SE Complexity Training 1.5 2.5 3.5 4.5 40 60 80 100 120 140 M SE Complexity Testing 0.2 0.4 0.6 0.8 1 1.2 70 80 90 100 110 120 130 140 150 160 170 180 190 M SE Complexity Training 0.2 0.4 0.6 0.8 1 1.2 70 80 90 100 110 120 130 140 150 160 170 180 190 M SE Complexity Testing 65 0.720 so với (0.934, 1.046) trên tập kiểm tra hoặc tập dữ liệu TR giá trị MSE là 0.068 so với (0.100, 0.132). Từ bảng 2.9 cho thấy kết quả phân tích thống kê bằng phương pháp kiểm định giả thuyết t-test với độ tin cậy 95% thì thuật toán chúng tôi đề xuất khác biệt thống kê so với các thuật toán trong [14] trên 3 tập dữ liệu WA, WI, STR trên tập dữ liệu kiểm tra, các tập dữ liệu còn lại mặc dù đạt kết quả tốt hơn nhưng không có sự khác biệt thống kê với các thuật toán được so sánh. - Về mục tiêu tính giải nghĩa được: Từ bảng 2.9 cho thấy các hệ luật được tạo ra có độ phức tạp thấp hơn so với các thuật toán trong [14] trên 5 tập dữ liệu. Độ dài trung bình của luật (Comp/#R) của các luật trong LRBS được tạo ra từ thuật toán HA-PAES-SG ngắn hơn nhiều so với với các thuật toán trong [14]. Cụ thể với tập dữ liệu WA thuật toán tạo ra LRBS có trung bình độ dài luật là 2.4 so với (3.72 và 6.46) hoặc tập dữ liệu WI chiều dài trung bình luật là 2.393 so với (3.467 và 6.368),. Từ đây chúng tôi có thể kết luận rằng, các LRBS được tạo ra từ thuật toán HA-PAES-SG có tính giải nghĩa được theo nghĩa độ phức tạp ở mức luật cao hơn các FRBS được tạo ra từ các thuật toán trong [14]. Ở mức phân hoạch mờ tính giải nghĩa được theo quan điểm của hướng tiếp cận dựa trên tập mờ cũng được đảm bảo do các phân hoạch mờ là phân hoạch mờ mạnh. Tuy nhiên ngữ nghĩa của các từ không bảo toàn được tính khái quát và tính đặc tả khi số từ sử dụng cho các biến thay đổi. Vì vậy, cần tìm một phương pháp biểu diễn ngữ nghĩa khác cho các từ. Từ yêu cầu này chúng tôi phát triển thuật toán HA-PAES-MG trong phần tiếp theo. Phân tích các kết quả trong bảng A.1, A.2 cũng cho kết quả tương tự như trong bảng 2.9. 2.2.3. Thuật toán HA-PAES-MG Trong phần này chúng tôi ph

Các file đính kèm theo tài liệu này:

  • pdfluan_an_hoang_van_thong_7091_1854509.pdf
Tài liệu liên quan