Ứ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

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