Một phương pháp thiết kế hệ phân lớp mờ dựa trên việc mở rộng lượng hóa dại số gia tử

MỘT PHƯƠNG PHÁP THIẾT KẾ HỆ PHÂN LỚP MỜ DựA TRÊN VIỆC
MỞ RỘNG LƯỢNG HÓA DẠI Số GIA TỬ*
PHẠM ĐÌNH PHONG1, NGUYỄN CÁT Hồ2, TRAN thái sơn2, nguyễn thanh thủy3
1Công ty Prévoir Việt Nam; Email: dinhphong_pham@gmail.com
2 Viện Công nghệ thông tin, Viện Hàn lâm KH và CNVN;
ncho@gmai.com; trn_thaison@yahoo.com
3 Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội; nguyenthanhthuy@vnu.edu.vn
Tóm tắt. Phương pháp lượng hóa đại số gia tử (ĐSGT) theo cách truyền thống [1-2] đã đem lại những thành công bưóc đầu trong ứng dụng ĐSGT vào bài toán thiết kế các hệ phân lóp mờ (HPLM) vói ngữ nghĩa tập mờ tam giác của các từ ngôn ngữ [3, 4, 11]. Ngữ nghĩa số của mỗi từ ngôn ngữ được xác định bởi giá trị định lượng ngữ nghĩa chỉ là một điểm, cho phép xác định đỉnh của tập mờ hình tam giác. Phương pháp lượng hóa ĐSGT mở rộng đã được công bố trong [10], được bổ sung thêm khả năng mô hình hóa ngữ nghĩa lõi của từ, cho phép xây dựng các phân hoạch trên miền các thuộc tính dựa trên chính các khoảng tính mờ mức k và cho phép định lượng ngữ nghĩa lõi của các từ dưói dạng khoảng được sử dụng để xác định đáy nhỏ của các tập mờ hình thang. Bài báo đề xuất một phương pháp thiết kế các từ ngôn ngữ và HPLM dạng luật vói ngữ nghĩa tập mờ của các từ mong muốn dạng hình thang dựa trên phương pháp lượng hóa ĐSGT mở rộng này và khảo sát tính hiệu quả của phương pháp lượng hóa mói khi giải quyết bài toán phân lóp. Kết quả thực nghiệm vói 10 tập dữ liệu mẫu chuẩn cho thấy phương pháp lượng hóa ĐSGT mói mềm dẻo hơn và cho kết quả tốt hơn.
Từ khóa. Hệ luật mờ phân lóp, phân hoạch mờ, đại số gia tử, ánh xạ định lượng khoảng.
Abstract. The conventional method of quantification of hedge algebras [1-2] has achieved some effective successes in its application to hedge algebras to the fuzzy classifier design problem using fuzzy set based semantics of linguistic terms in the form of triangle fuzzy sets [3, 4, 11]. The numeric semantic of a term defined by its semantically quantifying mapping value is a point which is relevant to define the vertex of the triangular fuzzy set. An extended quantification method of hedge algebras proposed in [10], using partitions of the feature spaces, based on a degree k semantically quantifying mapping intervals, allows to model the core semantics of a terms in the form of an interval, which is upper base of a trapezoidal fuzzy set. This paper proposes a method for designing linguistic terms and fuzzy rule based classifiers with trapezoidal fuzzy set semantics, based on this extended hedge algebras quantification and examines the effectiveness of the new quantification method in solving classification problems. The experimental results over 10 datasets have shown that the proposed method is more flexible and produces better results.
Key words. Fuzzy classification system, hedge algebras, fuzzy partition, interval semantically quantifying mapping.
MỞ ĐẦU
Trong những năm gần đây, hệ mờ dựa trẽn luật đã có những ứng dụng thành công trong nhiều lĩnh vực khác nhau. Hệ phân lớp mờ (HPLM) là trường hợp đơn giản nhất của hệ mờ
Bài báo được thực hiện với sự hỗ trợ từ quỹ phát triển KHCNVN (Nafosted), mã số 102.01-2011.06. dựa trẽn luật. Một hướng nghiên cứu trong lĩnh vực này đang được quan tâm là xây dựng HLPM dựa trên hệ luật mờ dạng if-then [3-9] và đã cho kết quả khá tốt so với các phương pháp khác.
Trong tiếp cận lý thuyết tập mờ [5-9], các tập mờ của các giá trị ngôn ngữ hầu hết là dạng tam giác cố định và các giá trị ngôn ngữ chỉ là nhãn được người thiết kế gán cho dựa trên cảm nhận trực giác, do đó chúng không thể phản ánh ngữ nghĩa của các giá trị ngôn ngữ tương ứng một cách thích đáng. Mặc dù hệ luật chứa các từ ngôn ngữ với ngữ nghĩa biểu thị bằng tập mờ, nhưng bài toán thiết kế các từ ngôn ngữ cùng với ngữ nghĩa của chúng trong phạm vi lý thuyết tập mờ lại chưa được đặt ra một cách rõ ràng.
ĐSGT cung cấp một cơ sỏ hình thức toán học cho việc mô hình hóa và thiết kế các từ ngôn ngữ cùng với ngữ nghĩa dựa trên tập mờ của chúng và có thể ứng dụng trong quá trình thiết kế tập giá trị ngôn ngữ cùng với ngữ nghĩa dựa trên tập mờ cho việc xây dựng tự động cơ sỏ luật của hệ phân lớp mờ. Phương pháp thiết HPLM với ngữ nghĩa ĐSGT [11] được chia làm hai giai đoạn. Giai đoạn thứ nhất là giai đoạn thiết kế tự động các từ ngôn ngữ cùng với ngữ nghĩa dựa trên tập mờ của chúng. Giai đoạn hai là giai đoạn xây dựng phương pháp trích rút hệ luật mờ tối ưu từ tập dữ liệu mẫu dựa trên ngữ nghĩa tích hợp với ngôn ngữ thu được ỏ giai đoạn trên. Giai đoạn thứ nhất đòi hỏi phải giải bài toán xây dựng các khoảng lân cận ngữ nghĩa của tập các từ trong X(k) có độ dài không lớn hơn k sao cho chúng lập thành phân hoạch của [0, 1]. Do cách lượng hóa truyền thống [3, 4] chấp nhận tiên đề ^2{fm(hx) : h 2 Hg = fm(x) dẫn đến các khoảng tính mờ của các hạng từ có độ dài k trong Xk đã đủ lấp đầy miền tham chiếu [0, 1] nên không còn không gian cho việc xây dựng các khoảng lân cận ngữ nghĩa cho các hạng từ có độ dài nhỏ hơn k, dẫn đến việc phải xây dựng hệ khoảng tương tự mức k [3, 4, 11]. Với phương pháp lượng hóa như vậy, các giá trị định lượng ngữ nghĩa có thể được xem như là ngữ nghĩa lõi của các từ và phù hợp với ý nghĩa của các đỉnh của các tập mờ tam giác tương ứng.
Để có thêm không gian cho việc xây dựng các khoảng lân cận ngữ nghĩa cho các hạng từ có độ dài nhỏ hơn k, trong [10] đã chấp nhận giả thiết 52 ffm(hx) : h 2 Hg < fm(x). Khi đó, gia tử ho được sử dụng trong việc mô tả ngữ nghĩa của hạng từ phụ thuộc ngữ cảnh, nó đáp ứng được yêu cầu hình thức hóa trong trình bày và mô tả được sự thay đổi ngữ nghĩa theo ngữ cảnh xác định bỏi sự hiện diện đồng thời với các hạng từ khác. Cách lượng hóa ĐSGT mỏ rộng này phép xây dựng các phân hoạch trên miền các thuộc tính dựa trên chính các khoảng tính mờ mức k do có đủ không gian để biểu diễn lân cận ngữ nghĩa của các hạng từ có độ dài nhỏ hơn k. Gia tử h0 được sử dụng để xây dựng giá trị định lượng khoảng của các từ ngôn ngữ, hox xác định ngữ nghĩa lõi của chúng. Đây chính là cơ sỏ cho phép xây dựng các tập mờ hình thang với đáy nhỏ là giá trị định lượng khoảng của các từ ngôn ngữ tương ứng.
Mục tiêu bài báo là chứng minh khả năng ứng dụng hiệu quả của phương pháp lượng hóa ĐSGT mỏ rộng vào bài toán thiết kế các từ ngôn ngữ cùng với ngữ nghĩa dựa trên tập mờ hình thang và xây dựng HPLM dạng luật. Việc phát triển phương pháp thiết kế tự động các từ ngôn ngữ sẽ dựa trên việc xây dựng các phân hoạch mờ của miền các thuộc tính, được thiết lập từ các khoảng tính mờ mức k trong ĐSGT mỏ rộng. Thuật toán xây dựng các luật mờ khỏi sinh cũng được cải tiến cho phù hợp với cách lượng hóa mới.
Bài báo được bố cục gồm 5 mục. Sau phần mỏ đầu, Mục 2 trình bày tóm tắt phương pháp lượng hóa ĐSGT mỏ rộng được đề xuất trong [10]. Mục 3 là trình bày phương pháp thiết kế ngôn ngữ gắn kết với ngữ nghĩa định lượng hình thang và thiết kế HPLM dạng luật dựa trên phương pháp định lượng ĐSGT mỏ rộng. Mục 4 trình bày các thử nghiệm và đánh giá. Và cuối cùng là kết luận.
MỞ RỘNG LƯỢNG HÓA ĐẠI Số GIA TỬ
ĐSGT là mô hình định tính nên để tính toán số được cần phải lượng hóa các đặc trưng của nó trên cơ sỏ ngữ nghĩa định tính. Có ba đặc trưng lượng hóa ĐSGT là độ đo tính mờ của ĐSGT, các khoảng tính mờ của các hạng từ và ánh xạ định lượng ngữ nghĩa. Trong [10] đề xuất phương pháp mỏ rộng các khái niệm này nhằm xây dựng một cơ sỏ hình thức hóa linh hoạt hơn mô tả được ngữ nghĩa phụ thuộc ngữ cảnh, cho phép mỏ rộng khả năng ứng dụng của ĐSGT. Mục này tóm tắt lại phương pháp lượng hóa ba đặc trưng này, làm cơ sỏ cho việc xây dựng phương pháp thiết kế các từ ngôn ngữ với ngữ nghĩa định lượng khoảng và tâp mờ hình thang.
Cho ĐSGT mỏ rộng AX * = (X * ,C,G,Hex, <) của một ĐSGT AX = (X;C;G;H; <), trong đó Hex = H u {ho}, ho 2 H, (xem [10]).
Một hàm fm : X* ! [0; 1] được gọi là độ đo tính mờ của ĐSGT AX* nếu nó thỏa các tính chất:
(fm1) fm(c ) + fm(W) + fm(c+) = 1;
(fm2) 22h2Hex fm(hu) = fm(u); 8u 2 H(G);
(fm3) 8h 2 Hex; fm(hy) fm(y) '
8x,y 2 H({c ,c+}) thỏa x,y = h0z với một z bất kì,
fm(hx)
fm(x)
Giả sử AX* là một ĐSGT tuyến tính mỏ rộng và một độ đo tính mờ fm : X* ! [0; 1] thỏa các tính chất trên. Khi đó, với mỗi k > 0, mỗi hạng từ x của X*k) được liên kết với một khoảng trong PI([0; 1]); tập tất cả các khoảng con của [0,1], được gọi là khoảng tính mờ mức k của x và nó được xây dựng quy nạp theo k như sau:
Với k = 1, xây dựng các khoảng tính mờ =i(c_); =i(W); =i(c+) với |=i(x)| = fm(x), sao cho chúng có thứ tự tương đồng với thứ tự của các hạng từ c~; W; c+.
Với k > 1; và x 2 C, ta xây dựng các khoảng tính mờ (x) sao cho:
Nếu |x| <k - 1 thì |=k(x)| = |=k-i(x)|.
Nếu |x| = k — 1 thì |=k(x)| = ụ.(h0)fm(x).
Nếu | x| = k thì |(x) | = fm(x).
Thứ tự của các khoảng tính mờ tương đồng với thứ tự của các hạng từ x.
Ta giả sử các khoảng tính mờ là đóng trái, chỉ có hằng có giá trị 1 là đóng cả hai đầu.
Ánh xạ định lượng ngữ nghĩa biểu diễn ngữ nghĩa lõi của các giá trị ngôn ngữ. Cho độ đo tính mờ fm của ĐSGT AX*. Khi đó ánh xạ định lượng khoảng f được định nghĩa như sau f (x) = =l(x)+i(hox) 2 PI[0; 1]; 8x 2 X* và l(x) là độ dài của x. Lưu ý rằng nếu x = h0Z; thì f (x) = =i(x)+i(hox) =	(hoz).
Vì ngữ nghĩa lõi của các từ ngôn ngữ được xác định bỏi các giá trị khoảng của ánh xạ định lượng khoảng của ĐSGT mỏ rộng được sử dụng trong mục sau để sinh ngữ nghĩa tập mờ hình thang của các từ ngôn ngữ của biến ngôn ngữ, nên ĐSGT mỏ rộng có thể được áp dụng trong việc giải quyết các bài toán ứng dụng khác nhau. Bài báo này sẽ chứng minh khả năng ứng dụng hiệu quả của chúng trong việc giải các bài toán phân lớp.
THIẾT KẾ HPLM DẠNG LUẬT VỚI NGỮ NGHĨA DựA TRÊN ĐẠI Số GIA TỬ
Tri thức của HPLM dạng luật trong bài báo này là một tập các luật mờ có trọng số có dạng
Luật Rq : IF X1 is Aqi AND ... AND Xn is Aq;n THEN Cq with CFq; với q = 1..N (3.1) trong đó X = {Xj;j = 1; ...,n} là tập n biến ngôn ngữ (thuộc tính) và Aq,j(j = 1; ...,n) là các nhãn ngôn ngữ của các điều kiện mờ trong tiền đề, Cq là tên lớp kết luận của Rq và N là số luật mờ, CFq là trọng số hay độ tin cậy của luật thứ q. Thông thường, một bài toán phân lớp P được cho bởi một tập dữ liệu mẫu phân lớp D gồm m mẫu dữ liệu được gán nhãn dp = [dp,1; dp,2;...; dp,n; Cp];P = 1;...; m, với n thuộc tính, M lớp kết luận (hay M nhãn) trong tập C = {Cq : q = 1; ...;M}. Luật Rq dạng (3.1) có thể được viết gọn lại thành Aq ) Cq with CFq, trong đó Aq là các tiền đề của luật thứ q và Cq là một nhãn lớp.
Giải bài toán thiết kế HPLM dạng luật là xây dựng phưong pháp trích rút một hệ luật mờ từ tập D cho HPLM sao cho đạt hiệu quả phân lớp cao đồng thời hệ luật thu được lại dễ hiểu đối với người dùng. Phưong pháp thiết kế HPLM dạng luật với ngữ nghĩa ĐSGT bao gồm hai bước:
Thiết kế tự động các hạng từ ngôn ngữ tối ưu và ngữ nghĩa dựa trên tập mờ của chúng đối với từng thuộc tính của tập dữ liệu mẫu với việc áp dụng giải thuật tiến hóa đa mục tiêu sao cho việc thiết kế là kết quả của sự tưong tác giữa ngữ nghĩa của các hạng từ và dữ liệu.
Trích rút các co sở luật mờ từ dữ liệu mẫu sao cho co sở luật mờ thu được có sự cân bằng hợp lý giữa hiệu quả phân lớp và tính dễ hiểu. Trên co sở tính đa dạng và tính phù hợp của các hạng từ thu được từ bước (1), mục tiêu của bước này là tìm giải pháp đạt được sự cân bằng (tradeoff) tối ưu giữa hiệu quả phân lớp và tính ít phức tạp và dễ hiểu của hệ luật trên co sở cân bằng giữa tính khái quát và tính riêng biệt của các hạng từ khi tưong tác với dữ liệu mẫu.
Đối với bài toán phân lớp cụ thể, để thiết kế các hạng từ cho đặc tính Fj, các dữ kiện sau cần được chỉ ra để sinh tập các hạng từ Xj,(kj) và để xác định các ngữ nghĩa tập mờ của chúng:
Các hạng từ sinh c~ và c+, tập các gia tử âm H~ = {hji : —qj < i < —1}, tập các gia tử dưong H+ = {hji : 1 < i < Pj}, gia tử ho. Trong nghiên cứu này chỉ sử dụng một gia tử âm và một gia tử dưong nên Pj = qj = 1.
Các ràng buộc của các tham số mờ để duy trì sự phù hợp ngữ nghĩa của các hạng từ
aj < fmj(e") < aj; bj < fmj(W) < bj; fmj(e") + fmj(W) + fmj(c+) = 1;
ej < ụ(hj,i) < ej; ^hj;i2Hj ụ(hj,i') = 1
và độ dài tối đa của các hạng từ kj < K, với K là một số nguyên dưong.
Thiết kế các hạng từ ngôn ngữ
Các nghiên cứu [3, 4, 11] cho thấy cú pháp và ngữ nghĩa của các hạng từ đóng vai trò rất quan trọng. Tuy nhiên, các cách tiếp cận trong phạm vi lý thuyết tập mờ, cú pháp và ngữ nghĩa định tính của các từ ngôn ngữ chưa được đề cập. Vì vậy, mục này trình bày việc thiết kế tối ưu các hạng từ mang ngữ nghĩa định tính cùng với ngữ nghĩa mờ của chúng cho bài toán phân lớp mờ và nó là co sở để tạo ra các luật mờ với ngữ nghĩa dễ hiểu đối với người sử dụng.
Phương pháp lượng hóa ĐSGT mỏ rộng là cơ sỏ hình thức hóa cho phép ngữ nghĩa định tính xác định hàm định lượng ngữ nghĩa khoảng [10] và dùng h0X để sinh khoảng ngữ nghĩa lõi của hạng từ X, đồng thời, nó xác định các khoảng tính mờ của các từ của thuộc tính. Với ngữ nghĩa định lượng khoảng và khoảng tính mờ của các từ ta có thể xây dựng ngữ nghĩa tập mờ. Trong nghiên cứu này chúng là các tập mờ hình thang. Đây là đặc trưng làm cho cách tiếp cận ĐSGT khác biệt với cách tiếp cận dựa trên tập mờ.
Phương pháp luận trên được áp dụng vào việc thiết kế các hạng từ ngôn ngữ với ngữ nghĩa dựa trên tập mờ có độ dài tối đa là kj cho bài toán phân lớp mờ như sau:
+ Đối với mỗi thuộc tính j của tập dữ liệu mẫu được liên kết với một ĐSGT AXj, tiến hành xây dựng tập các hạng từ Xj;(kj) có độ dài nhỏ hơn hoặc bằng kj và có thứ tự theo ngữ nghĩa định tính của chúng.
+ Với mỗi 0 < k < kj, giả sử Xj;k = {xj;i : i = 1;...; Njkg với thứ tự Xj;1 < ... < Xj;Njk và ký hiệu Jj là tập các tham số mờ của AXj. Với các giá trị cụ thể của các tham số mờ trong Jj, xây dựng các khoảng tính mờ =k(Xj;i) mức k và các giá trị định lượng ngữ nghĩa f (Xj;i) đối với các hạng từ trong Xj;k [10] và các đại lượng này hoàn toàn được xác định. Các khoảng tính mờ =k(Xj;i) thỏa mãn thứ tự =k(Xj;i) < ... < =k(xjNjk) và tạo thành một phân hoạch của [0, 1]. Ví dụ, Hình 3.1 biểu diễn hệ khoảng tính mờ với kj = 2 của một ĐSGT có 2 gia tử, trong đó L 2 H~ và V 2 H+.
$1C
S1(W)
S1(C+)
Hệ khoảng tính mờ của các hạng từ ngôn ngữ mức k = 1
 ————,..... 0	S2(Vc)	-92(c)	S2(Lẽ)	S2(W)
	————4*————H
S2(Lc+)	S2(c+)	S2(Vc+)
Hệ khoảng tính mờ của các hạng từ ngôn ngữ mức k = 2
Hình 3.1. Hệ khoảng tính mờ của các hạng từ ngôn ngữ với kj = 2
Theo [10] thì f (Xji) C =(Xj;i) xác định giá trị định lượng ngữ nghĩa khoảng của hạng từ Xji biểu thị khoảng định lượng ngữ nghĩa lõi của Xj;i. Ta có thể dùng nó làm đáy nhỏ của tập mờ hình thang của từ Xji do các giá trị trong khoảng đó phù hợp với ngữ nghĩa định tính của từ nhất. Đối với các hạng từ Xji có độ dài nhỏ hơn k thì f (Xj;i) = =k(Xji), có độ dài bằng k thì f(Xji) = =k+i(h0Xj;i).
Để lập luận phân lớp cho các mẫu dữ liệu dựa trên hệ luật mờ dạng (3.1) bằng phương pháp lập luận Single Winner Rule [7, 8 , 11], mỗi giá trị ngôn ngữ được gán một hàm định lượng ngữ nghĩa. Với ngữ nghĩa định lượng khoảng và phương pháp phân hoạch trên miền thuộc tính theo các khoảng tính mờ được xác định ỏ trên, hàm định lượng ngữ ng ... được sử dụng phổ biến là tích (c.s) của độ tin cậy (c) và độ hỗ trợ (s). Độ tin cậy được tính theo công thức (3.4), độ hỗ trợ được tính theo công thức sau [7, 8, 11]
s(Aq ) Ch) = X VAq{dp)/n.	(3.6)
dp2Ch
Như vậy, sau Bước 3 ta thu được hệ luật khỏi sinh S0 có NR0 = NB0 * M luật. Trong quá trình lập luận, các luật được gán một trọng số (rule weight). Theo [7, 8, 11], trọng số luật được tính bằng công thức
CF(Aq ) Cq)= Cq - Cqt2nd,	(3.7)
trong đó, cq là độ tin cậy của luật Rq và cq;2nd là độ tin cậy lớn nhất của các luật có cùng tiền đề điều kiện Aqnhưng kết luận là lớp khác với Cq
cq,2nd = rnax{c(Aq ) Ch)|h = 1, ...; M; Ch = Cq}•
So với thủ tục xây dựng tập luật khỏi sinh trong [11], tại Bước 1 các ánh xạ định lượng điểm truyền thống được thay thế bằng các ánh xạ định lượng khoảng, các tập mờ hình tam giác được thay thế bằng các tập mờ thang. Tại Bước 2, các khoảng tính mờ mức kj được sử dụng làm phân hoạch trên miền các thuộc tính thay cho các khoảng tưong tự mức kj.
Độ phức tạp của thủ tục xây dựng các luật khỏi sinh là đa thức đối với kích thước và số thuộc tính của tập dữ liệu mẫu D như đã được chứng minh trong [11].
Tối ưu hóa tham số ngữ nghĩa của các hạng từ ngôn ngữ và tối ưu hóa hệ luật
Kết quả của bất kỳ phưong pháp tiếp cận theo hệ mờ dựa trên luật nào cũng phụ thuộc vào các tham số mờ. Với phưong pháp thiết kế HLPM dựa trên hệ luật mờ theo tiếp cận lý thuyết tập mờ [6-9], các tác giả sử dụng các chiến lược tìm kiếm tối ưu các tham số mờ, cụ thể là hiệu chỉnh các tham số của tập mờ dạng tam giác bằng giải thuật di truyền. Với phưong pháp thiết kế HLPM dạng luật theo tiếp cận ĐSGT [11], các tác giả đã phân tích sự phụ thuộc của kết quả phân lớp của hệ luật vào các tham số mờ gia tử (tham số ngữ nghĩa) và sử dung giải thuật di truyền lai SGA với việc đánh trọng số các hàm mục tiêu để hiệu chỉnh các tham số này cho từng tập dữ liệu mẫu cụ thể. Sau khi có được bộ tham số mờ gần tối ưu, tiến hành tạo sinh hệ luật khỏi sinh làm đầu vào cho thủ tục tối ưu hóa hệ luật mờ do các tiêu chuẩn sàng được áp dụng không cho kết quả tốt. Với phưong pháp lượng hóa ĐSGT mỏ rộng, bài báo sử dụng giải thuật tối ưu hóa bầy đàn đa mục tiêu PSO (Particle Swarm Optimization) với hàm thích nghi chia sẻ [12], định hướng việc tìm kiếm các cá thể trong tối ưu toàn cục (mặt Pareto hay Pareto front), để tìm kiếm tối ưu các tham số ngữ nghĩa và tối ưu hóa hệ luật. Nhờ đó các mục tiêu tối ưu được chia sẻ bình đẳng thông qua hệ số chia sẻ và kết quả là một tập các phưong án.
Tập các tham số cần được hiệu chỉnh thích nghi đối với bài toán thiết hệ phân lớp mờ P dựa trên phưong pháp lượng hóa ĐSGT mỏ rộng là các tham số ngữ nghĩa trong P. Chúng bao gồm các độ đo tính mờ fmj(c~) của hạng từ sinh c~ và của hằng fmj(W); các độ đo tính mờ của các gia tử của thuộc tính j và tham số kj nguyên dưong hạn chế độ dài của các từ ngôn ngữ được thiết kế của thuộc tính j. Có thể thấy so với phưong pháp tối ưu hóa trong
, phương pháp được đề nghị ỏ đây có nhiều hơn hai tham số hiệu chỉnh thích nghi cho mỗi thuộc tính j: tham số độ đo tính mờ của Wj và tham số độ đo tính mờ của gia tử hj;o.
Để hiệu chỉnh thích nghi các tham số ngữ nghĩa được nêu ỏ trẽn cho phù hợp với từng tập dữ liệu mẫu, bài toán tiến hóa tối ưu hóa đa mục tiêu thiết kế các từ ngôn ngữ tối ưu cho bài toán phân lớp P được đặt ra là [11] với V(n,D,No) là thủ thục xây dựng hệ luật khỏi sinh và với các ràng buộc về các tham số ngữ nghĩa đã được nêu ỏ trên. Khi đó, mục tiêu của bài toán đặt ra là tối đa hóa hiệu quả phân lớp và tối thiểu hóa độ dài trung bình các luật của P.
Như đã được đề cập ỏ trên, giải thuật PSO được sử dụng để tìm kiếm giá trị tối ưu của các tham số ngữ nghĩa cho bài toán phân lớp mờ cụ thể P với cơ sỏ luật S. Thủ tục tối ưu hóa các tham số nghĩa được đặt tên là MPSO_SPO. Các mục tiêu của bài toán tối ưu hóa là
maximize perf (S) và maximize avg(S)_1 với ràng buộc S c S0.	(3.8)
trong đó perf (S) là tỷ lệ phân lớp đúng của hệ S trên tập mẫu huấn luyện, avg(S)_1 là nghịch đảo của độ dài luật trung bình của hệ S. Số luật dùng để tối ưu hóa các tham số ngữ nghĩa được cố định trước theo từng tập dữ liệu mẫu cụ thể nên không nằm trong các mục tiêu cần tối ưu hóa.
Sau quá trình tối ưu hóa tham số các tham số ngữ nghĩa bằng giải thuật MPSO_SPO ta thu được các tham số gần tối ưu nopt. Sử dụng thủ tục xây dựng luật khỏi sinh để sinh tập luật khỏi sinh S0 với N Ro luật sử dụng các tham số nopt. Có thể sử dụng các tiêu chuẩn sàng để lựa chọn một tập luật cho HPLM dạng luật từ tập luật So. Tuy nhiên, việc sử dụng các tiêu chuẩn sàng có thể cho tập luật không đạt được các mục tiêu (3.8) tốt. Bài toán đặt ra là phải chọn ra một tập luật con của So cho HPLM sao cho đạt các mục tiêu sau
maximize perf (S), maximize NR(S)_1 và maximize avg(S)_1 với ràng buộc
S c So, NR(S) < Nmax.	' (3.9)
trong đó NR(S)_1 là nghịch đảo của số luật trung bình và Nmax là số luật chọn tối đa và được cho trước. Ta gọi bài toán này là bài toán tối ưu hóa hệ luật. Tiếp tục sử dụng giải thuật tiến hóa đa mục tiêu PSO cho bài toán tối ưu hóa hệ luật với ba hàm mục tiêu cụ thể trong (3.9). Thủ tục tối ưu hóa hệ luật được đặt tên là MPSO_RBO.
Để lựa chọn các tập luật con từ So cho việc sinh các cá thể cho giải thuật MPSO_RBO, phương pháp mã hóa số thực được sử dụng. Mỗi cá thể ứng với mỗi lời giải là một tập luật S được chọn từ So và được biểu diễn bỏi một chuỗi số thực ri = (p1, ...,PNmax), Pj 2 [0,1]. Giá trị pj xác định chỉ số của luật trong So được chọn cho S có giá trị là pj X |So|, ta có 0 < pj X |So| < |So|.
S = {Ri 2 So|i = bpj X | So |J, i > 0g	(3.10)
trong đó L*J là phép lấy phần nguyên.
Do giải thuật tối ưu hóa hệ luật cho một tập dữ liệu mẫu cụ thể có áp dụng phương pháp tìm kiếm tối ưu Pareto nên cho kết quả là một tập các phương án. Từ tập các phương án tìm được ta chọn ra một phương án với tập luật cho kết quả phân lớp trên tập huấn luyện cao nhất. Nếu có nhiều phương án giống nhau thì chọn ngẫu nhiên một phương án.
KẾT QUẢ THỰC NGHIÊM VÀ ĐÁNH GIÁ
Mục này trình bày các kết quả thực nghiệm của hệ phân lớp đối với một số tập dữ liệu mẫu chuẩn được cung cấp bỏi KEEL-Dataset repository ( Mỗi tập dữ liệu mẫu được chia thành 10 phần bằng nhau sẵn có từ liên kết trẽn. Tiến hành lấy lần lượt từng phần để kiểm tra (tập kiểm tra), toàn bộ 9 phần còn lại được dùng để sinh luật (tập huấn luyện). Mỗi tập dữ liệu mẫu được chạy thử nghiệm 3 lần 10-folds theo cách như trên, ta có kết quả của 30 lần chạy. Kết quả cuối cùng của các lần thử nghiệm sau khi tối ưu hóa hệ luật được tính trung bình đối với số luật #R, độ phức tạp của hệ luật #C, tỷ lệ phân lớp đúng trên tập huấn luyện Ptr và trên tập kiểm tra Pte. Độ phức tạp của hệ luật được tính theo công thức #C = #R X Avg, trong đó Avg là độ dài trung bình của hệ luật.
Trong bài toán thực nghiệm, số gia tử âm và gia tử dương đều được lấy là 1. Giả sử gia tử âm là L và gia tử dương là V. Các ràng buộc của các tham số ngữ nghĩa bao gồm: giới hạn độ dài của các hạng từ kj < 3; 0; 2 < fmj(c“) < 0; 7; 0; 0001 < fmj(W) < 0; 2; fmj(c“) + fmj (W) + fmj(c+) = 1; 0; 2 < ụ,j(L) < 0; 7; 0; 0001 < ụ.j(ho) < 0; 5. Giá trị của các tham số này được chọn là kết quả của nhiều lần thực nghiệm với các giá trị khác nhau của các tham số đối với một số tập dữ liệu mẫu trên cơ sỏ đánh giá sự cân bằng giữa hiệu quả phân lớp và sự cân đối giữa miền giá trị của fmj(c~) và fmj(c+).
Các tham số cho thuật toán MPSO_SPO gồm: số thế hệ tối đa: 250; số cá thể mỗi thế hệ: 600; Hệ số Inertia: 0,4; hệ số nhận thức cá nhân 0,2; hệ nhận thức xã hội: 0,2; Số luật khỏi sinh bằng số thuộc tính; giới hạn độ dài của luật là 1; Thực hiện toán tử đột biến khi tỷ lệ di chuyển của các cá thể nhỏ hơn 70%.
Các tham số cho thuật toán MPSO_RBO như sau: Số thế hệ tối đa: 1000; số cá thể mỗi thế hệ: 600; Hệ số Inertia: 0,4; hệ số nhận thức cá nhân 0,1; hệ số nhận thức xã hội: 0,1; Thực hiện toán tử đột biến khi tỷ lệ di chuyển của các cá thể nhỏ hơn 70%; Hệ số chia sẻ các hàm thích nghi được tính tự động; Số luật khỏi đầu |S0| = 300 X số lớp; giới hạn độ dài của luật đối với tập dữ liệu mẫu có số thuộc tính lớn hơn 30 là 2, ngược lại là 3.
Phương pháp lập luận được sử dụng là Single Winner Rule [8].
Kết quả chạy thực nghiệm của phương pháp được đề xuất và so sánh với kết quả của phương pháp lượng hóa truyền thống [11] được thể hiện trong Bảng 1.
Bảng 1. Kết quả chạy 3x10 — folds trẽn 10 tập mẫu được thử nghiệm
Tập dữ liệu mẫu
Lượng hóa sử dụng ngữ nghĩa hình thang
Lượng hóa sử dụng ngữ nghĩa tam giác
So sánh
Stt
Tên
#R
#Rx#
C
Ptr
Pte
#R
#Rx
#C
Ptr
Pte
' p-
^#Rx#
C
1
Bands
7,00
78,17
76,28
72,10
6,00
83,40
75,57
70,63
1,47
-5,23
2
Bupa
8,97
170,65
77,54
69,41
8,97
196,37
77,40
67,71
1,7
-25,72
3
Dermatology
10,87
189,45
96,88
95,52
10,93
194,61
98,82
95,52
0
-5,16
4
Haberman
4,00
20,00
77,67
77,43
3,00
13,30
76,78
75,11
2,32
6,7
5
Pima
5,97
50,32
78,53
76,66
5,00
51,17
79,03
75,70
0,96
-0,85
6
Sonar
5.97
53,89
86,84
77,29
7,00
84,00
88,59
76,73
0,56
-30.11
7
V ehicle
11,03
216,26
71,64
68,12
11,93
324,98
70,59
67,46
0,66
-108,72
8
Wdbc
4,97
41,56
97,40
95,85
4,97
45,86
96,51
94,90
0,95
-4,3
9
Wine
5,87
42,06
100,0
98,52
5,73
65,17
99,79
98,30
0,22
-23,11
10
Wisconsin
6,93
57,55
96,74
96,45
5,97
67,42
98,38
96,72
-0,27
-9,87
Trong Bảng 1, cột gộp “So sánh” gồm cột “= Pte” thể hiện phần trăm tăng hiệu quả phân lớp của phương pháp được đề xuất so với phương pháp lượng hóa truyền thống đối với từng tập dữ liệu mẫu, cột “ = #R X #C” thể hiện sự chênh lệch độ phức tạp của hệ luật. Kết quả cho thấy, phương pháp được đề xuất cho kết quả phân lớp cao hơn đối với hầu hết các tập dữ liệu mẫu được thực nghiệm, đồng thời có độ phức tạp thấp hơn rất nhiều so với phương pháp lượng hóa truyền thống [11]. Cụ thể, hiệu quả phân lớp tăng 8.57% và độ phức tạp của hệ luật giảm 18,32%.
Bảng 2. So sánh hiệu suất phâ n lớp củ a HPLM sử dụng Wilcoxon với m ức a = 0; 05
vs
R+
R
Exact P-value
Asymp. P-value
Confidence interval
Exact confidence
Lượng hóa sử dụng ngữ nghĩa tam giác
43,0
2,0
0,011718
0,012851
[0,33,1,47]
0,95118
Bảng 3. So sánh độ phức tạp của hệ luật sử dụng Wilcoxon với mức a = 0; 05
PS
R-
Exact P-value
Asymp. P-value
Confidence interval
Exact confidence
Lượng hóa sừ dụng ngữ nghĩa tam giác
50,0
5,0
0,019532
0,019059
[-54,785 , -3,005]
0,95118
Thực hiện phương pháp kiểm tra Wilcoxon Signed Rank [13, 14] sử dụng dữ liệu trong Bảng 1 để so sánh kết quả của hai phương pháp. Các kết quả kiểm tra hiệu suất phân lớp và độ phức tạp của hệ luật lần lượt được thể hiện trong Bảng 2 và Bảng 3. Với giá trị R~ là tổng các xếp hạng ứng với các hiệu quả phân lớp của phương pháp lượng hóa ĐSGT mỏ rộng nhỏ hơn giá trị găng (critical value) ứng với số tập dữ liệu mẫu Nds = 10 và p = 0; 05 bằng 8 (có thể tham khảo trong bảng phân phối T Wilcoxon (bảng B.12 trong [14])) nên ta có thể khẳng định rằng phương pháp thiết kế HPLM dạng luật với phương pháp lượng hóa ĐSGT mỏ rộng không những cho hiệu quả tốt phân lớp hơn mà còn có độ phức tạp của hệ luật thu được giảm đáng kể so với phương pháp lượng hóa ĐSGT truyền thống.
KẾT LUẬN
Bài báo đề xuất và phát triển phương pháp thiết kế HPLM dạng luật dựa trên ĐSGT mỏ rộng được đề xuất trong [10] và tiến hành nghiên cứu thử nghiệm phương pháp thiết kế đối với một số tập dữ liệu mẫu chuẩn được cung cấp bỏi KEEL-Dataset repository. Phương pháp lượng hóa ĐSGT mỏ rộng cho phép xây dựng các phân hoạch trên miền các thuộc tính dựa trên chính các khoảng tính mờ mức k và cho phép định lượng ngữ nghĩa lõi của các từ ngôn ngữ dưới dạng khoảng. Đây chính là cơ sỏ cho phép xây dựng các tập mờ hình thang với đáy nhỏ là giá trị định lượng khoảng của các từ ngôn ngữ. So với tập mờ hình tam giác thì tập mờ hình thang có miền tin cậy rộng hơn và hai cạnh bên có độ dốc lớn hơn nên cho tỷ lệ mất mát thông tin ít hơn. Kết quả thử nghiệm trên 10 tập dữ liệu mẫu cho hiệu quả phân lớp của HPLM được đề xuất cao hơn với độ phức tạp nhỏ hơn so với HPLM sử dụng phương pháp lượng hóa truyền thống. Điều đó chứng tỏ rằng phương pháp được đề xuất không chỉ có một cơ sỏ lí thuyết chặt chẽ mà còn hứa hẹn tạo ra một khả năng ứng dụng tiềm năng.
TÀI LIÊU THAM KHẢO
N. C. Ho and N. V. Long, Fuzziness measure on complete hedges algebras and quantifying semantics of terms in linear hedge algebras, Fuzzy Sets and Systems 158 (2007) 452-471.
Nguyen Cat Ho, Tran Thai Son, Tran Dinh Khang, Le Xuan Viet, Fuzziness measure, quantified semantic mapping and interpolative method of approximate reasoning in medical expert systems, Journal of Computer Science and Cybernetics 18 (3) (2002) 237-252.
Nguyễn Cát Hồ, Trần Thái Sơn, Dương Thăng Long, Tiếp cận đại số gia tử cho phân lóp mờ, Tạp chí Tin học và Điều khiển học 25 (1) 2009 53-68.
Dương Thăng Long, Một phương pháp xây dựng hệ luật mờ có trọng số để phân lóp dựa trên đại số gia tử, Tạp chí Tin học và Điều khiển học 26 (1) (2010) 55-72.
A. Fernandez, M. Calderón, E. Barrenechea, H. Bustince F. Herrera, Enhancing fuzzy rule based systems in multi-classification using pairwise coupling with preference relations, EU- ROFUSE09 Workshop on Preference Modelling and Decision Analysis Pamplona, Spain, September 16-18, 2009 (39-46).
Chen Ji-lin, Hou Yuan-long, Xing Zong-y, Jia Li-min, Tong Zhong-zhi, A multi-objective geneticbased method for design fuzzy classification systems, IJCSNS International Journal of Computer Science and Network Security 6 (8A) (August 2006) 110-118.
H. Ishibuchi and T. Yamamoto, Rule weight specification in fuzzy rule-based classification systems, IEEE Trans. on Fuzzy Systems 13 (4) (2005) 428-435.
H. Ishibuchi, T. Yamamoto, Fuzzy rule selection by multi-objective genetic local search algorithms and rule evaluation measures in data mining, Fuzzy Sets and Systems 141 (1) (2004) 59-88.
Rafael Alcalá, Yusuke Nojima, Francisco Herrera, Hisao Ishibuchi, Multi-objective genetic fuzzy rule selection of single granularity-based fuzzy classication rules and its interaction with the lateral tuning of membership functions, Journal Soft Computing 15 (12) (December 2011) 2303-2318.
Nguyễn Cát Hồ, Trần Thái Sơn, Phạm Đình Phong, Định lượng ngữ nghĩa khoảng của Đại số gia tử vói việc bổ sung một gia tử đặc biệt, Tạp chí Tin học và Điều khiển học 28 (4) (2012) 346-358.
Cat Ho Nguyen, Witold Pedrycz, Thang Long Duong, Thai Son Tran, A genetic design of linguistic terms for fuzzy rule based classifiers, International Journal of Approximate Reasoning, Elsevier Science Inc 54 (1) (January 2013) 1-21.
Maximino Salazar Lechuga, “Multi-Objective Optimisation using Sharing in Swarm Optimisation Algorithms”, Doctor thesis, School of Computer Science, The University of Birmingham, 2006.
Janez Demsar, Statistical comparisons of classifiers over multiple data sets, Journal of Machine Learning Research 7 (2006) 1-30.
J. Zar, Biostatistical Analysis, Prentice-Hall, Upper Saddle River, NJ, 1999.
Ngày nhận bài 21 - 3 - 2013 Nhận lại sau sửa ngày 27 - 11 - 2013