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
131 trang |
Chia sẻ: mimhthuy20 | Lượt xem: 527 | Lượt tải: 1
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ếucó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:
- luan_an_hoang_van_thong_7091_1854509.pdf