Ứng dụng phân cụm trừ mờ cho bài toán nhận dạng hệ điều khiển tự động từ dữ liệu

Trần Mạnh Tuấn và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 116 (02): 73 - 77<br /> <br /> ỨNG DỤNG PHÂN CỤM TRỪ MỜ<br /> CHO BÀI TOÁN NHẬN DẠNG HỆ ĐIỀU KHIỂN TỰ ĐỘNG TỪ DỮ LIỆU<br /> Trần Mạnh Tuấn1*, Lê Bá Dũng2<br /> 1<br /> <br /> Trường ĐH Công nghệ thông tin và Truyền thông - ĐHTN<br /> 2<br /> Viện Công Nghệ Thông tin<br /> <br /> TÓM TẮT<br /> Các hệ thống mờ có ứng dụng rộng rãi trong nhiều lĩnh vực, đặc biệt là trong lĩnh vực mô phỏng<br /> quá trình và điều khiển. Các hệ thống mờ có thể đƣợc thiết kế từ tri thức chuyên gia hoặc từ dữ<br /> liệu. Mỗi phƣơng pháp thiết kế đều có những thuận lợi và hạn chế riêng của nó. Trong bài báo này<br /> chúng tôi trình bày quá trình xây dựng hệ luật mờ cho hệ mờ từ dữ liệu trong nhận dạng các hệ<br /> động lực học. Có nhiều cách tiếp cận khác nhau nhƣng bài báo tập trung vào phân tích phƣơng<br /> pháp phân cụm trừ để tạo ra các luật mờ.<br /> Từ khóa: phân cụm trừ mờ, hệ nhận dạng, điều khiển mờ<br /> <br /> PHẦN MỞ ĐẦU*<br /> Sự phát triển nhanh chóng các hệ thống thông<br /> tin nhƣ hiện nay, thì hệ mờ đƣợc áp dụng<br /> thành công trong nhiều lĩnh vực nhƣ điều<br /> khiển tự động, phân lớp dữ liệu, phân tích<br /> việc ra quyết định, các hệ chuyên gia, các cơ<br /> sở dữ liệu mờ. Hệ luật mờ xây dựng từ tri<br /> thức nói chung hay hệ suy luận mờ nói riêng<br /> đƣợc xây dựng theo suy diễn của con ngƣời,<br /> là một phần quan trọng trong ứng dụng logic<br /> mờ cũng nhƣ trong lý thuyết tập mờ vào thực<br /> tế. Có nhiều tác giả đã sử dụng các phƣơng<br /> pháp dựa theo phân lớp dữ liệu, phân cụm dữ<br /> liệu, xây dựng cây quyết định...[2,3,4,5] vào<br /> xây dựng hệ mờ của các hệ thống thông minh,<br /> hệ hỗ trợ ra quyết định. Hệ mờ đƣợc thực<br /> hiện từ các luật mờ và các luật mờ này đƣợc<br /> xây dựng từ tri thức của các chuyên gia trong<br /> một lĩnh vực cụ thể.<br /> Phân cụm dữ liệu đang là một vấn đề quan<br /> tâm nghiên cứu của các tác giả trong và ngoài<br /> nƣớc [2,3,4,5] và có nhiều thuật toán phân<br /> cụm đƣợc đề xuất. Trong đó, một số thuật<br /> toán phân cụm đƣợc sử dụng kết hợp với giải<br /> thuật di truyền trong quá trình thực hiện. Một<br /> cách tiếp cận khác mà bài báo nêu ra đó là xây<br /> dựng hệ luật mờ từ dữ liệu cho nhận dạng hệ<br /> điều khiển. Bài báo trình bày theo các phần:<br /> *<br /> <br /> Tel: 0983 668841, Email: tmtuan@ictu.edu.vn<br /> <br /> i) Mở đầu, ii)Tiếp cận hệ thống: đƣa ra cái<br /> nhìn khái quát của bài toán trong quá trình<br /> xây dựng luật từ dữ liệu. Đề xuất một phƣơng<br /> pháp tiếp cận là phân cụm trừ mờ. iii) Mô hình<br /> mờ và Kết quả thực nghiệm iv) Kết luận.<br /> TIẾP CẬN HỆ THỐNG<br /> Hệ điều khiển mờ<br /> Giả sử chúng ta có tập dữ liệu với cỡ p đầu<br /> vào và q đầu ra trong hệ điều khiển mờ có hệ<br /> luật mờ có các luật nhƣ dƣới đây. Theo<br /> Sugeno ở luật thứ i trong hệ luật đƣợc viết<br /> theo[2]:<br /> Ri: If x1 is A1i and x2 is A2i and... and xp is<br /> A ip then yi is p0i+p1i x1+....+ppi xp<br /> (1)<br /> Trong đó:<br /> xi là các biến vào<br /> <br /> Aij là giá trị ngữ nghĩa của biến đầu vào<br /> yi là hàm tuyến tính<br /> <br /> p ij là các thông số của hàm tuyến tính đầu ra<br /> Các biến đầu vào x1, x2 ...là các biến thể hiện<br /> các đại lƣợng vật lý của hệ thống, cũng có thể<br /> là thời gian xử lý và độ ƣu tiên (hoặc trọng<br /> số) trong khi biến đầu ra yk (với k = 1, 2, …,<br /> K) là đại lƣợng vật lý của đầu ra, có thể là chỉ<br /> số khả năng lựa chọn (hoặc chỉ số tuần tự)<br /> của luật k. A1k và A2k (với k = 1, 2, …, K) là<br /> các giá trị ngữ nghĩa của phần điều kiện của<br /> luật k nhận đƣợc bằng cách chiếu các cụm<br /> vào các miền của các đại lƣợng vật lý đầu vào<br /> 73<br /> <br /> Trần Mạnh Tuấn và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> hoặc là thời gian xử lý và độ ƣu tiên tƣơng<br /> ứng và pik (với i = 1, 2; k = 1, 2, …, K) là<br /> các hằng của hàm tuyến tính đầu ra theo<br /> Sugeno.<br /> Phân cụm trừ<br /> Phân cụm trừ (subtractive clustering - SC)<br /> xác định các tâm cụm dựa trên mật độ các<br /> điểm lân cận. Xét một tập hợp dữ liệu gồm n<br /> điểm [3]:<br /> <br /> X  x1 , x2 ,..., xn <br /> <br /> (2)<br /> <br /> Hàm tính mật độ cho một điểm dữ liệu là:<br /> 4<br /> <br /> n<br /> <br /> Pi<br /> <br /> e<br /> <br /> xi<br /> <br /> ra2<br /> <br /> xj<br /> <br /> 116 (02): 73 - 77<br /> <br /> cụm thứ k, trong đó  và  lần lƣợt đƣợc<br /> gọi là hằng số chấp nhận và hằng số từ chối,<br /> thƣờng đƣợc chọn lần lƣợt là 0.5 và 0.15.<br /> Một tâm cụm mới đƣợc chọn nếu điểm đó có<br /> mật độ lớn hơn cận trên. Nếu điểm có mật độ<br /> lớn nhất nhỏ hơn cận dƣới thì thuật toán<br /> dừng. Phân cụm trừ bao gồm các thông số<br /> <br />  ,  ,  , ra . Các thông số đó<br /> đƣợc chọn nhƣ sau: 0.3≥ ra ≥0.15;<br /> <br /> chủ yếu sau<br /> thƣờng<br /> <br /> 1.5≥  ≥1.25.<br /> <br /> Biểu diễn thuật toán: Các bƣớc của thuật toán<br /> nhƣ sau<br /> <br /> 2<br /> <br /> (3)<br /> Bước 1: Khởi tạo<br /> <br /> j 1<br /> <br /> ra<br /> <br /> ,<br /> <br /> <br /> <br /> với  <br /> <br /> .<br /> <br /> rb<br /> ,<br /> ra<br /> <br /> Trong đó:<br /> <br /> và<br /> <br /> Pi: Mật độ các điểm bao quanh điểm dữ liệu<br /> thứ i.<br /> <br /> Bước 2: Tính mật độ cho các điểm dữ liệu<br /> theo công thức (3). Chọn điểm có mật độ lớn<br /> <br /> ra: là một hằng số dƣơng hay còn gọi là bán<br /> kính cụm.<br /> Chuẩn . : Khoảng cách Euclide giữa điểm<br /> dữ liệu thứ i với các điểm bao quanh.<br /> <br /> nhất làm tâm cụm thứ nhất P1*<br /> <br /> Khi mật độ của tất cả các điểm dữ liệu đã<br /> đƣợc tính, lựa chọn điểm có mật độ lớn nhất<br /> làm tâm cụm thứ nhất. Gọi x1* là vị trí tâm<br /> cụm đầu tiên, có mật độ là P1* thì P1* đƣợc<br /> xác định theo<br /> n<br /> <br /> P1*  max Pi<br /> <br /> Tính lại mật độ cho các điểm dữ liệu theo<br /> 2<br /> 4<br /> công thức:<br />  2 xi  x1*<br /> rb<br /> *<br /> Pi  Pi  P1 e<br /> ; i  1,..., n<br /> (4)<br /> Và rb thƣờng đƣợc chọn là rb 1.5ra , tiếp<br /> tục chọn điểm có mật độ lớn nhất làm tâm<br /> cụm thứ 2.<br /> Trong trƣờng hợp tổng quát khi đã có k tâm<br /> cụm thì mật độ của các điểm dữ liệu còn lại<br /> đƣợc tính theo công thức:<br /> <br /> <br /> Pi  Pi  P e<br /> <br /> 4<br /> xi  xk*<br /> rb2<br /> <br /> 2<br /> <br /> ; i  1,..., n<br /> <br /> (5)<br /> <br /> ref<br /> Sử dụng 2 điểm cận là cận dƣới * P<br /> và<br /> <br /> ref<br /> cận trên  * P , với Pref là mật độ của tâm<br /> <br /> 74<br /> <br /> i 1<br /> <br /> *<br /> 1<br /> <br /> x là tâm cụm thứ nhất .<br /> Bước 3: Tính toán lại mật độ cho các điểm dữ<br /> liệu còn lại theo công thức (4).<br /> Bước 4: Gọi x* là điểm có mật độ lớn nhất là<br /> P*.<br /> - Nếu P*   Pref : x<br /> mới và tiếp tục bƣớc 3.<br /> <br /> *<br /> <br /> là một tâm cụm<br /> <br /> - Ngƣợc lại nếu P*   P ref : chuyển sang<br /> <br /> i 1<br /> <br /> *<br /> k<br /> <br /> n<br /> <br /> max Pi và<br /> <br /> <br /> <br /> bƣớc 5<br /> - Ngƣợc lại:<br /> + dmin khoảng cách nhỏ nhất giữa x * và<br /> các tâm cụm trƣớc đó.<br /> + Nếu<br /> <br /> d min<br /> ra<br /> <br /> P*<br /> P ref<br /> <br /> 1 : x * là một tâm cụm<br /> <br /> mới và tiếp tục bƣớc 3.<br /> + Ngƣợc lại:<br /> <br /> Thiết lập P( x* ) 0 .<br /> Chọn x* có mật độ P* lớn nhất và tiếp tục<br /> bƣớc 4.<br /> Bước 5: Đƣa ra các cụm kết quả. Khi đó, độ<br /> thuộc của điểm xi đối với một tâm cụm thứ k<br /> đƣợc xác định theo công thức (6):<br /> <br /> Trần Mạnh Tuấn và Đtg<br /> 4<br /> ik<br /> <br /> e<br /> <br /> ra2<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> xi<br /> <br /> xk<br /> <br /> 2<br /> <br /> (6)<br /> <br /> Nhận dạng hệ thống mờ<br /> Giả sử các tâm cụm c của các cụm đƣợc thể<br /> hiện M*= {m1*, m2*,....... mc*} trong không<br /> gian L chiều, với N chiều đầu vào, ta sẽ có LN chiều đầu (hình 1a). Từ đó tâm cụm M* sẽ<br /> đƣợc chia ra theo (hình 1b)<br /> <br /> a) Các hàm thuộc hình thành qua phân cụm<br /> <br /> 116 (02): 73 - 77<br /> <br /> Hàm f(.) không đƣợc biết trƣớc có dạng:<br /> f (u) 0.6Sin( u) 0.3Sin(3 u) 0.1Sin(5 u) (8)<br /> Để có thể nhận dạng đƣợc hệ động lực học<br /> trên, ta sử dụng một hệ mô hình mẫu dạng:<br /> <br /> y(k 1) 0.3 y(k ) 0.6 y(k 1) F (u(k )) (9)<br /> trong đó y (k 1) , y (k ) , y (k 1) là các giá<br /> trị ƣớc lƣợng ở thời điển thứ k-1, k, k+1<br /> F(u(k)) là hàm ƣớc lƣợng qua quá trình phân<br /> cụm trừ mờ cho các dữ liệu vào ra hình 2, hệ<br /> luật mờ đƣợc hình thành với các luật nhƣ trên<br /> H3, tín hiệu điều khiển u(k) với<br /> u (k ) Sin(2 k / 250) cho quá trình ƣớc lƣợng<br /> từ thời k=1 đến thời điển k=250 sau đó thay<br /> đổi đến k=500:<br /> <br /> u (k )<br /> <br /> 0.5Sin(2 k / 250) 0.5Sin(2 k / 25)<br /> <br /> 10<br /> 5<br /> 0<br /> -5<br /> -10<br /> <br /> b) Các tâm điểm của các giá trị ngữ nghĩa<br /> Hình 1. Dạng hàm thuộc cho phân cụm<br /> <br /> 100<br /> <br /> 150<br /> <br /> 200<br /> <br /> 250<br /> <br /> 300<br /> <br /> 350<br /> <br /> 400<br /> <br /> 450<br /> <br /> 500<br /> <br /> 0<br /> <br /> 50<br /> <br /> 100<br /> <br /> 150<br /> <br /> 200<br /> <br /> 250<br /> <br /> 300<br /> <br /> 350<br /> <br /> 400<br /> <br /> 450<br /> <br /> 500<br /> <br /> 0<br /> -5<br /> -10<br /> <br /> Hình 2. Dữ liệu vào ra của hệ thống<br /> <br /> Hệ luật mờ cho nhận dạng hệ điều khiển trên<br /> Hình 3.<br /> <br /> Hình 3. Hệ luật qua phân cụm<br /> TIN HIEU THUC xanh, TIN HIEU MO HINH do<br /> <br /> U<br /> <br /> 10<br /> 5<br /> 0<br /> <br /> QUÁ TRÌNH THỰC NGHIỆM<br /> <br /> -5<br /> <br /> Mô hình nhận dạng hệ phi tuyến<br /> <br /> -10<br /> <br /> Giả sử mô hình động học của hệ điều khiển<br /> có dạng mô tả toán học nhƣ sau:<br /> <br /> y(k 1) 0.3 y(k ) 0.6 y(k 1)<br /> <br /> 50<br /> <br /> 5<br /> <br /> Định lý: Giả sử hệ thống suy diễn mờ f(x) với<br /> số lƣợng bất kỳ các giá trị ngữ nghĩa, có thể là<br /> dạng tam giác, dạng chuông…có tâm điểm mji<br /> trên ai, bi i=1…N và trên khoảng đó ít nhất<br /> một và nhiều nhất là hai các giá trị ngữ nghĩa<br /> khác không. Cũng giả sử là g(x): RNR là<br /> hàm chƣa biết bất kỳ, và nếu g(x) là hàm liên<br /> tục và khả vi trên U =[a1, b1]x[a2,<br /> b2]x….x[aN, bN] thì hệ mờ f(x) có thể xấp xỉ<br /> hàm g(x) với độ chính xác bất kỳ ε với ε> 0 ,<br /> ε đƣợc gọi là sai số chấp nhận đƣợc ||g(x)f)x)|| ∞ ≤ ε<br /> Khi đó ||.||∞ đƣợc định nghĩa ||e(x)||∞=supx<br /> |e(x)|<br /> <br /> 0<br /> <br /> 10<br /> <br /> f (u (k ))<br /> <br /> (7)<br /> Với y(k) và u(k) là các tín hiệu ra và vào của<br /> hệ thống tại thời điểm thứ k.<br /> <br /> 0<br /> <br /> 50<br /> <br /> 100<br /> <br /> 150<br /> <br /> 200<br /> <br /> 250<br /> <br /> 300<br /> <br /> 350<br /> <br /> 400<br /> <br /> 450<br /> <br /> 500<br /> <br /> 350<br /> <br /> 400<br /> <br /> 450<br /> <br /> 500<br /> <br /> Sai so mo hinh<br /> 1<br /> 0.5<br /> 0<br /> -0.5<br /> -1<br /> <br /> 0<br /> <br /> 50<br /> <br /> 100<br /> <br /> 150<br /> <br /> 200<br /> <br /> 250<br /> <br /> 300<br /> <br /> Hình 4. Kết quả mô phỏng<br /> <br /> 75<br /> <br /> Trần Mạnh Tuấn và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Kết quả mô phỏng cho thấy sự hội tụ giữa hai<br /> mô hình toán học và mô hình nhận dạng hệ<br /> thống qua phân cụm. Kết quả mô phỏng trên<br /> cũng cho thấy sự hội tụ nhanh của mô hình<br /> nhận dạng, một điều quan trọng thể hiện tính<br /> xấp xỉ của các mô hình tính toán mềm có độ<br /> chính xác tùy ý với các mô hình thực.<br /> KẾT LUẬN<br /> Bài báo trình bày một thuật toán nhận dạng hệ<br /> điều khiển theo phân cụm trừ mờ từ dữ liệu.<br /> Các kết quả của thuật toán đƣợc mô phỏng<br /> cho hệ. Các kết quả mô phỏng cho thấy thuật<br /> toán nhận dạng hay hệ luật đề xuất đáp ứng<br /> đƣợc các chỉ tiêu của quá trình nhận dạng hệ<br /> thống. Việc thiết kế các hệ điều khiển nói<br /> chung hay các hệ thống mờ nói riêng từ dữ<br /> liệu là một trong những quan tâm rộng lớn<br /> trong thời gian gần đây và rất phù hợp với<br /> thực tế và đây cũng là một hƣớng nghiên cứu<br /> mới cần đƣợc quan tâm.<br /> Ký hiệu<br /> <br /> A1i , A2i ..<br /> Y<br /> <br /> p ij<br /> ra<br /> x1, x2…<br /> <br /> <br /> <br /> <br /> rb<br /> *<br /> <br /> Ký hiệu<br /> Ý nghĩa<br /> Các giá trị ngôn ngữ<br /> hàm tuyến tính đầu ra<br /> Các thông số hàm tuyến<br /> tính đầu ra<br /> Bán kính cụm<br /> Tập các điểm dữ liệu<br /> Hằng số chấp nhận<br /> Hằng số từ chối<br /> <br /> 1.5ra<br /> <br /> Thông số chọn theo ra<br /> giá trị đặt, giá trị cần<br /> <br /> TÀI LIỆU THAM KHẢO<br /> 1. Trần Mạnh Tuấn, Lê Bá Dũng, (2013) Markov<br /> model in proving the convergence of fuzzy genetic<br /> algorithm, tạp chí Khoa học và Công nghệ - Viện<br /> Hàn lâm Khoa học và Công nghệ Việt Nam, tập 51,<br /> số 3, , trang 267-277.<br /> <br /> 76<br /> <br /> 116 (02): 73 - 77<br /> <br /> 2. S. L. Chiu, (1994), Fuzzy Model Identification<br /> Based on Cluster Estimation, Journal on Intelligent<br /> Fuzzy Systems, vol. 2, pp.267_278.<br /> 3. S. L. Chiu, (1997) Extracting Fuzzy Rules from<br /> Data for Function Approximation and Pattern<br /> Classification, Fuzzy Information Engineering: a<br /> Guide Tour of Applications, pp.149_162 (Chapter 9).<br /> D.Dubois, H. Prade, R.R. Yager (Eds.), Wiley, New<br /> York.<br /> 4. Demirli, K., S. X. Cheng, and P. Muthukumaran,<br /> (2003) Subtractive Clustering Based Modeling of<br /> Job Sequencing with Parametric Algorithm,<br /> Information Technology Journal 7 JunYing Chen,<br /> Zheng Qin and Ji Jia,A Weighted Mean Subtractive<br /> Clustering (2): 356-360, ISSN 1812-5638,<br /> 2008.Search, Fuzzy Sets<br /> and Systems. 137: 235-270.<br /> 5. Mohammad GhasemiGol, Hadi Saoghi Yazdi,<br /> Reza Monsefi, (2010) A New Hierarchical<br /> Clustering Algorithm on Fuzzy Data (FHCA),<br /> International Journal of coputer and electrical<br /> engineering, Vol.2, No.1, February.<br /> 6. Agus Priyono, Muhammad Ridwad Jais Alias,<br /> Riza<br /> AtiQ<br /> O.K.Rahmat,<br /> Azmi<br /> Hassan,<br /> Mohd.Alauddin Mohd.Ali, Generation of fuzzy rules<br /> with subtractive clusterring, Universiti Teknologi<br /> Malaysia, Jurnal Teknologi, 43(D) Dis.2005:143-153<br /> 7. Siamak Tafazoli, Mathieu Leduc and Xuehong<br /> Sun, (September 2006) Hysteresis Modeling using<br /> Fuzzy Subtractive Clutering, International Journal of<br /> Computational Cognition, Vol.4, No.3.<br /> 8.<br /> C.D.Doan,<br /> S.Y.Liong<br /> and<br /> Dulakshi<br /> S.K.Karunasinghe, (07.4.2005) Derivation of<br /> effective and effcient data set with subtractive<br /> clustering method and genetic algorithm, Journal of<br /> Hydroinfomatics.<br /> 9. Lothar M.Schmitt, (2001), Fundamental Study<br /> Theory of genetic algorithms, Theoretical Computer<br /> Science 59 1-61<br /> 10. Gunter Rudolph, (January 1994) Convergence<br /> Analysis of Canonical Genetic Algorithms, IEEE<br /> transaction on neural networks, vol.5, No.1.<br /> 11. Mohanad Alata, Mohammad Molhim, and<br /> Abdullah Ramini, (2008), Optimizing of Fuzzy CMeans Clustering Algorithm Using GA, World<br /> Academy<br /> of<br /> Science,<br /> Engineering<br /> and<br /> Technology, pages 224-229, 39.<br /> <br /> Trần Mạnh Tuấn và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 116 (02): 73 - 77<br /> <br /> SUMMARY<br /> AN APPLICATION OF FUZZY SUBSTRACTIVE CLUSTERING<br /> FOR IDENTIFICATION CONTROLLED SYSTEMS FROM DATA<br /> Tran Manh Tuan1*, Le Ba Dung2<br /> 1<br /> <br /> College of Information and Communication Technology – TNU,<br /> 2<br /> Institute of Information Technology<br /> <br /> Fuzzy system is applied in various fields, in which fuzzy control fuzzy identification is widely<br /> focussed. Usually, fuzzy system designed from knowledge of experts in the certain application<br /> fields or from data. Each approach has some advantages and some limitations. In this paper, we<br /> describe substractive clustering method to create fuzzy rules<br /> Keywords: Fuzzy substractive clustering, identification system, fuzzy control.<br /> <br /> Ngày nhận bài:25/01/2014; Ngày phản biện:10/02/2014; Ngày duyệt đăng: 26/02/2014<br /> Phản biện khoa học: TS. Vũ Đức Thái – Trường ĐH Công nghệ Thông tin & Truyền thông - ĐHTN<br /> *<br /> <br /> Tel: 0983 668841, Email: tmtuan@ictu.edu.vn<br /> <br /> 77<br /> <br />