Rút gọn tập luật mờ trích xuất từ máy học Véc-tơ hỗ trợ bằng cách tích hợp thuật toán phân cụm k-Means

Nội dung text: Rút gọn tập luật mờ trích xuất từ máy học Véc-tơ hỗ trợ bằng cách tích hợp thuật toán phân cụm k-Means

1. 230 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Rút gọn tập luật mờ trích xuất từ máy học Véc-tơ hỗ trợ bằng cách tích hợp thuật toán phân cụm k-Means Nguyễn Đức Hiển1 1 Trường Cao đẳng Công nghệ thông tin, Đại học Đà Nẵng ndhien@cit.udn.vn Tóm tắt. Mô hình mờ TSK và mô hình máy học véc-tơ hỗ trợ hồi quy có sự tương đương nhau trong một số điều kiện nhất định. Bằng cách thỏa mãn các điều kiện đề đồng nhất các hàm đầu ra của mô hình mờ TSK và máy học véc-tơ hỗ trợ hồi quy, chúng ta có thể xây dựng một thuật toán cho phép trích xuất mô hình mờ TSK từ máy học véc-tơ hỗ trợ. nghiên cứu này đề xuất một giải pháp trích xuất tập luật mờ TSK từ máy học véc tơ hỗ trợ, trong đó có kết hợp giải pháp phân cụm K-Means để rút gọn tập luật. Hiệu quả của giải pháp đề xuất được đánh giá thông qua các kết quả thực nghiệm và có sự so sánh với kết quả của một số thực nghệm trên mô hình khác. Từ khóa: Mô hình mờ TSK, Máy học Véc-tơ hỗ trợ, Mô hình mờ hướng dữ liệu. 1 Đặt vấn đề Mô hình mờ được biết đến như là một mô hình khá hiệu quả trong việc xử lý những thông tin mơ hồ và không chắc đó chắn; đồng thời nó cũng thể hiện những lợi thế rõ ràng trong việc biểu diễn và xử lý tri thức. Hoạt động của mô hình mờ phụ thuộc nhiều vào hệ thống các luật mờ và quá trình suy diễn trên tập luật mờ đó. Đã có nhiều tác giả nghiên cứu và đề xuất các phương thức để xây dựng các mô hình mờ hướng dữ liệu [3, 4, 5, 6, 7, 8, 9, 10]. Vấn đề trích xuất mô hình mờ từ máy học véc-tơ hỗ trợ (SVM - Support Vector Machine) được nhóm tác giả J.-H Chiang và P. Y Hao nghiên cứu và công bố lần đầu tiên trong [3]. Một trong những vấn đề của máy học véc-tơ hỗ trợ là tính chính xác của mô hình thu được tỷ lệ thuận với số lượng support-vector (Sv) sinh ra; điều này đồng nghĩa với việc số lượng luật mờ của mô hình mờ trích xuất được sẽ tăng lên. Nói cách khác là khi tăng hiệu suất của mô hình thì đồng nghĩa với việc làm giảm tính “sáng sủa” (tính “có thể hiểu được”) của mô hình. Như vậy vấn đề đặt ra là làm thế nào có thể trích xuất được hệ thống mờ đảm bảo độ tin cậy của kết quả dự đoán, đồng thời hạn chế được số lượng luật mờ trong mô hình. Trong nghiên cứu này, chúng tôi đề xuất giải pháp tích hợp thuật toán phân cụm k-Means để rút gọn tập luât mờ trích xất được, đồng thời có thể đảm bảo được độ tin cậy của kết quả dự đoán dựa vào mô hình trích xuất được. Các phần tiếp theo của nghiên cứu bao gồm: phần 2 trình bày sơ lược về sự tương đương của mô hình mờ TSK và máy học véc-tơ hỗ trợ làm cơ sở cho việc xây dựng thuật toán trích xuất mô hình mờ. Phần 3 giới thiệu thuật toán fm-SVM* cho phép trích xuất tập luật mờ rút gọn từ SVM, trong đó có tích hợp thuật toán phân cụm K-Mean. Phần 4 trình bày những kết quả thực nghiệm của mô hình đề xuất, trong đó có kết hợp so sánh với một số kết quả của mô hình đề xuất trước đó. Cuối cùng, trong phần 5 chúng tôi nêu lên một số kết luận và định hướng nghiên cứu tiếp theo.
2. Nguyễn Đức Hiển 231 2 Sự tương đồng của mô hình mờ TSK và máy học véc-tơ hỗ trợ Hệ thống mờ TSK bao gồm một tập các luật mờ “IF - THEN”, với phần kết luận của mỗi luật này là một hàm (không mờ) ánh xạ từ các tham số đầu vào tới tham số đầu ra của mô hình [3,4,5,6,10]. Giả sử có một hệ thống mờ TSK với m luật mờ được biểu diễn như sau: j j j Rj : IF x 1 is A 1 and x 2 is A 2 and  and x n is A n THEN z gj x,x, 1 2  ,x n , j 1 , 2,  , m (1) Trong đó xi i 1, 2, n là các biến điều kiện; z là các biến quyết định của hệ thống mờ j được xác định bởi hàm gj . ; A i là những thuật ngữ ngôn ngữ xác định bởi hàm thành viên tương ứng μj x . Lưu ý, μj x là hàm thành viên mờ được xác định trên một véc-tơ Ai Ai nhiều chiều. Đầu ra của hệ thống mờ được tính toán như sau: m zj  x  j 1 A j f x m (2)  x  j 1 A j Với n j x  j xi (3) AA i i 1 j Trong đó, z là giá trị đầu ra của hàm g(. ). Bên cạnh đó, với vai trò giải quyết vấn đề tối ưu hóa hồi quy, lý thuyết cơ bản của SVM có thể được vắn tắt như sau [2,3,6,8]: Cho một tập dữ liệu huấn luyện x,y1 1 ,  , x,y l l   X  , trong đó X xác định miền dữ liệu đầu vào. Với ε-Support Vector Regression, bài toán tối ưu hóa ràng buộc cần giải quyết là: 1 l minwT w C   * (4) * i i w,,, b    2 i 1 T Sao cho: w .Φ xi b y i ε ξ i , T* * yi w .Φ x i b ε ξ i , với ξi ,ξ i 0, và i 1, 2,  , l * Trong đó, C là tham số chuẩn tắc,  là sai số cho phép, ξi , ξi là những biến lỏng, Φ(x) là hàm ánh xạ phi tuyến tính để tiền xử lý dữ liệu phi tuyến tính đầ vào bằng cách ánh xạ và không gian thuộc tính nhiều chiều ℱ. Và từ đó đưa đến việc giải bài toán Quadratic Programming: l 1 T )( x .  x  i i j j i j 2 i, j max (5) , * l l  y  i i  i i i i 1 i 1
3. 232 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Sao cho: l  i i 0, and C i , i 0, i 1, 2,  , l i 1 ∗ Trong đó, α, α là những nhân tử Lagrange. Véc-tơ w có dạng: l * (6) w  i i . x i i 1 Và hàm quyết định là: l f x *  xT .  x b (7)  i i i j i 1 Gọi Kx, x = Φ(x) . Φx là hàm nhân của không gian đầu vào; và hàm quyết định (7) được viết lại như sau: l * (8) f x  i i K x i , x b i 1 ∗ Những điểm đầu vào x với (α − α ) ≠ 0 được gọi là những véc-tơ hỗ trợ (SVs). Xét hàm đầu ra của mô hình mờ TSK (2) và hàm quyết định của mô hình máy học Véc-tơ hồi quy (8). Để (2) và (8) đồng nhất với nhau, trước tiên chúng ta phải đồng nhất giữa hàm nhân trong (8) và hàm thành viên trong (2). Ở đây, để thỏa mãn điều kiện Mercer [1] hàm thành viên Gauss được chọn làm hàm nhân; đồng thời giá trị của b trong (8) phải bằng 0. Khi hàm Gauss được chọn làm hàm thành viên và hàm nhân, đồng thời số luật mờ bằng với số véc-tơ hỗ trợ (m = l) thì hàm quyết định (8) trở thành: 2 l * 1 xi x f x i i exp (9)  2  i 1 i và hàm kết quả đầu ra suy luận mờ (2) trở thành: 2 l 1 x x z j exp j  j 1 2  j f x (10) 2 l 1 x x exp j  j 1 2  j Như cách biến đổi trong [8], hàm suy luận mờ (10) có thể viết lại như sau: 2 l 1 x x f x z j exp j (11)  2  j 1 j j * Và chúng ta chọn: z αi α i (12)
4. Nguyễn Đức Hiển 233 Như vậy, trên cơ sở thỏa mãn các điều kiện để đồng nhất hàm đầu ra của SVMs và hệ thống mờ TSK, chúng ta có thể trích xuất được mô hình mờ TSK từ máy học Véc-tơ hỗ trợ. 3 Thuật toán trích xuất tập luật mờ rút gọn từ SVM bằng cách tích hợp thuật toán phân cụm K-Means Từ những phân tích trên, chúng tôi đã đề xuất thuật toán fm-SVM* cho phép trích xuất mô hình mờ TSK từ máy học véc-tơ hỗ trợ gồm các bước nhưu sau: - Bước 1: huấn luyện SVMs với tập dữ liệu huấn luyện để trích xuất ra các véc-tơ hỗ trợ ∗ tương ứng với các giá trị = , phương sai , và ( − ) = . - Bước 2: dùng thuật toán K-Means để phân cụm các (, ) thành k cụm. - Bước 3: chọn các (, ) là trung tâm của các cụm để thiết lập các hàm thành viên Gauss cho các luật mờ TSK; trong đó là trung tâm của hàm thành viên và là biên độ mờ. Tập các luật mờ TSK trích xuất được sẽ có dạng: IF xi is Gaussmf  i , sv i THEN y i is B Sơ đồ thuật toán fm-SVM* được thể hiện ở Hình 1. Begin Input: Training data set Initialize parameters of SVMs Centers : , = 1. . Variances : , = 1. . Cluster (, ) using k-Means extract fuzzy rules from SVM IF x is Gaussmf(, ) THEN y is B Output: TSK fuzzy model End Hình 1. Mô hình thuật toán trích xuất tập luật mờ TSK
5. 234 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” 4 Kết quả thực nghiệm Để đánh giá thuật toán fm-SVM* đã đề xuất, chúng tôi xây dựng một hệ thống thử nghiệm dựa trên bộ công cụ Matlab. Trong thuật toán fm-SVM* chúng tôi có sử dụng: 1) Thuật toán học SVM của thư viện LIBSVM được phát triển bởi nhóm của Chih-Chung Chang [11], được sử dụng để sản xuất ra các SVs, làm cơ sở để trích xuất các luật mờ. 2) Hàm công cụ kmeans trong Matlab [13] được sử dụng để phân cụm các SVs. Ngoài ra, chúng tôi sử dụng hàm AVALFIS trong thư viện công cụ Matlab Fuzzy Logic để thực hiện suy luận dựa trên các luật mờ trích xuất được. Bên cạnh đó, trong thực nghiệm chúng tôi có kết hợp sử dụng thuật toán trích xuất luật mờ f-SVM* đã nghiên cứu đề xuất trong [12] để so sánh và đánh giá kết quả. 4.1 Ví dụ hồi quy phi tuyến tính Với trường hợp thực nghệm này, chúng tôi tiến hành xây dựng bộ dữ liệu dựa trên bài toán hồi quy phi tuyến sau: sin x if x o Sinc x x (13) 1 if x 0 Tập dữ liệu huấn luyện được xác định trong phạm vi từ −3π đến +3π. Với 1.000 mẫu dữ liệu sinh ra, 800 mẫu dữ liệu được sử dụng để huấn luyện cho máy học Véc-tơ hỗ trợ và sinh ra các luật mờ, 200 mẫu dữ liệu còn lại được sử dụng để thử nghiệm suy luận dựa trên tập luật mờ trích xuất được. Kết quả dự đoán với 200 mẫu dữ liệu, dựa trên tập luật trích xuất được với số lượng luật khác nhau, đánh giá qua thông số RMSE (Root Mean Squared Error), thể hiện ở Bảng 1. Tập luật mờ trích xuất được trong trường hợp gom thành cụm, tương ứng với 6 luật thể hiện ở Bảng 2. Bảng 1. So sánh kết quả các mô hình qua thông số RMSE - 4.1 Mô hình áp dụng Số luật mờ f-SVM* fm-SVM* 50 <10-10 <10-10 10 0,0011 0,0015 8 0,0010 0,0014 6 0,0183 0,0122 4 0,0553 0,0586 Bảng 2. Tập luật trích xuất được trong trường hợp gom thành 6 cụm - 4.1 Thứ tự Luật R1 if x is Gaussmf(0.69, -2.502) then y = 0,425 R2 if x is Gaussmf(0.73, -1.820) then y = -1,732 R3 if x is Gaussmf(0.70, -0.582) then y = 1,25 R4 if x is Gaussmf(0.75, 0,580) then y = 1,27 R5 if x is Gaussmf(0.72, 1.815) then y = -1,721 R6 if x is Gaussmf(0.74, 2.861) then y = 0,412
6. Nguyễn Đức Hiển 235 4.2 Ví dụ mô hình dự đoán chuỗi hồi qui hỗn loạn Mackey-Glass Với trường hợp thưc nghiệm này, chúng tôi lựa chọn thử nghiệm trên dữ liệu chuỗi thời gian Mackey-Glass (Mackey-Glass time series). Dữ liệu chuỗi thời gian Mackey-Glass được sinh theo công thức sau: ax t  x cx t (14) 1 xb t  Trong đó ta chọn τ = 30 , = 0,2, = 10, và = 0,1. Với 1.000 mẫu dữ liệu sinh ra, 800 mẫu dữ liệu được sử dụng để huấn luyện cho máy học Véc-tơ hỗ trợ và sinh ra các luật mờ, 200 mẫu dữ liệu còn lại được sử dụng để thử nghiệm suy luận dựa trên tập luật mờ trích xuất được. Thuộc tính đầu vào được lựa chọn là giá trị ( − 1), ( − 2), thuộc tính đầu ra cần dự đoán là giá trị (). Như vậy mô hình có 02 đầu vào và 01 đầu ra. Bảng 3 thể hiện kết quả dự đoán trên 200 mẫu dữ liệu thử nghiệm, đánh giá thông qua thông số RMSE. Kết quả 9 luật học được từ 800 mẫu dữ liệu huấn luyện trong trường hợp gom thành 9 cụm, tương ứng với 9 luật, thể hiện trong Bảng 4. Bảng 3. So sánh kết quả các mô hình qua thông số RMSE - 4.2 Mô hình áp dụng Số luật mờ f-SVM* fm-SVM* 170 <10-10 <10-10 9 0,0073 0,0078 6 0,0080 0,0082 5 0,0090 0,0082 4 0,0091 0,0095 3 0,0091 0,0103 2 0,0188 0,0205 Bảng 4. Tập luật trích xuất được trong trường hợp gom thành 9 cụm - 4.2 Thứ tự Luật R1 if x(t-2) is Gaussmf(0,54, 0.40) and x(t-1) is Gaussmf(0,50, 1,11) then x(t) is 1,08 R2 if x(t-2) is Gaussmf(0,52, 0,44) and x(t-1) is Gaussmf(0,56, 0,53) then x(t) is 1,12 R3 if x(t-2) is Gaussmf(0,55, 0,50) and x(t-1) is Gaussmf(0,55, 1,50) then x(t) is 0,95 R4 if x(t-2) is Gaussmf(0,56, 1,02) and x(t-1) is Gaussmf(0,55, 0,51) then x(t) is 1,22 R5 if x(t-2) is Gaussmf(0,60, 1,05) and x(t-1) is Gaussmf(0,58, 1,14) then x(t) is 0,98 R6 if x(t-2) is Gaussmf(0,63, 1,10) and x(t-1) is Gaussmf(0,54, 1,43) then x(t) is 1,05 R7 if x(t-2) is Gaussmf(0,51, 1,27) and x(t-1) is Gaussmf(0,55, 0,53) then x(t) is 1,14 R8 if x(t-2) is Gaussmf(0,56, 1,34) and x(t-1) is Gaussmf(0,62, 0,99) then x(t) is 0,98 R9 if x(t-2) is Gaussmf(0,55, 1.38) and x(t-1) is Gaussmf(0,57, 1,36) then x(t) is 1,02 5 Kết luận Nghiên cứu này chúng tôi đề xuất một hướng tiếp cận tích hợp thuật toán phân cụm k-Means vào quá trình trích xuất hệ thống mờ từ máy học Véc-tơ hỗ trợ hồi quy. Máy học Support-vector
7. 236 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” cung cấp một framework để trích xuất ra các Véc-tơ hỗ trợ làm cơ sở để hình thành các luật mờ. Trong nghiên cứu, chúng tôi đã phân tích mối quan hệ tương đương giữa mô hình máy học Véc-tơ hỗ trợ hồi quy và mô hình mờ TSK, để làm cơ sở cho việc xây dựng thuật toán trích xuất mô hình mờ TSK từ máy học Véc-tơ hỗ trợ hồi quy. Bên cạnh đó, để có thể trích xuất được tập luật rút gọn, chúng tôi đã đề xuất thuật toán fm-SVM* dựa trên giải pháp tích hợp thuật toán phân cụm k-Means với quá trình trích xuất tập luật mờ từ tập Véc-tơ hỗ trợ. Kết quả thực nghiệm trên dữ liệu thử nghiệm cho thấy được hiệu quả của mô hình đề xuất. Mặt khác, với tập luật rút gọn trích xuất được, sẽ góp phần làm giảm độ phức tạp của quá trình dự đoán dựa trên tập luật học được. Ngoài ra, tập luật rút gọn cũng làm tăng tính “sáng sủa” mô bình mờ, các chuyên gia con người có thể đọc hiểu và phân tích được tập luật này, và từ đó có thể đánh giá tập luật mờ và có thể có giải pháp để tối ưu hóa tập luật. Trong định hướng nghiên cứu tiếp theo, chúng tôi sẽ ứng dụng thuật toán trích xuất luật mờ fm-SVM* để xây dựng các mô hình mờ tích hợp giải quyết một số bài toán dự đoán, dự báo. Các mô hình mờ tích hợp này có thể được xây dựng dựa trên cơ sở phân tích ngữ nghĩa các luật mờ “có thể hiểu được” học được từ dữ liệu để từ đó tối ưu hóa tập luật và lựa chọn bổ sung một số luật thu thập được từ chuyên gia con người. Tài liệu tham khảo 1. J. Shawe-Taylor and N. Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, 2004. 2. Corinna Cortes and Vladimir Vapnik, Support-Vector Networks, Machine Learning, 20, 273-297 1995. 3. J.-H Chiang, P.-Y Hao, Support vector learning mechanism for fuzzy rule-based modeling: a new approach, IEEE Trans. On Fuzzy Systems, vol. 12, pp. 1-12, 2004. 4. J.L. Castro, L.D. Flores-Hidalgo, C.J. Mantas, J.M. Puche, Extraction of fuzzy rules from support vector machines, Elsevier. Fuzzy Sets and Systems, 158, 2057–2077, 2007. 5. J.-S. R. Jang, Anfis: adaptive-network-based fuzzy inference system, IEEE Transactions on Systems, Man and Cybernetics, vol. 23, no. 3, pp. 665-685 (1993). 6. David Martens, Johan Huysmans, Rudy Setiono, Jan Vanthienen, Bart Baesens, Rule Extraction from Support Vector Machines - An Overview of issues and application in credit scoring, Studies in Computational Intelligence (SCI) 80: 33–63, 2008. 7. M. Azeem, M. Hanmandlu, N. Ahmad, Generalization of adaptive neuro-fuzzy inference systems, IEEE Transactions on Neural Networks, vol. 11, no. 6. 8. S. Chen, J. Wang, D. Wang, Extraction of fuzzy rules by using support vector machines, IEEE, Computer society, pp. 438-441, 2008. 9. Serge Guillaume, Luis Magdalena, Expert guided integration of induced knowledge into a fuzzy knowledge base, Soft Comput, Springer-Verlag 2006, 10:733-784, 2006. 10. Y. Jin, B. Sendhoff, Extracting interpretable fuzzy rules from RBF networks, Neural Processing Letters, vol. 17, no. 2, pp. 149-164, 2003. 11. Chih-Wei Hsu, Chih-Chung Chang, Chih-Jen lin, A practical Guide to Support Vector Classification. (2010) 12. Nguyễn Đức Hiển, Lê Mạnh Thạnh, Cải thiện mô hình mờ hướng dữ liệu với tri thức tiên nghiệm, Kỷ yếu Hội thảo CITA’2016 (2016). 13. K-means clustering, truy cập lần cuối 2017/11/05.