Ứng dụng mẫu thiết kế xây dựng mô hình giải một số bài toán hồi quy - Nguyễn Mạnh Đức

Nguyễn Mạnh Đức Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 129 - 135 129 ỨNG DỤNG MẪU THIẾT KẾ XÂY DỰNG MÔ HÌNH GIẢI MỘT SỐ BÀI TOÁN HỒI QUY Nguyễn Mạnh Đức* Trường Đại học Sư phạm – ĐH Thái Nguyên TÓM TẮT Bài toán hồi quy được sử dụng nhiều trong khoa học kỹ thuật, kinh tế-xã hội phục vụ cho các công việc như phân tích xu hướng tiến triển của các các hiện tượng, tính toán tối ưu hóa, công tác dự báo... Trong công nghệ phần mềm, mẫu thiết kế là một giải pháp tổng thể cho các vấn đề chung trong thiết kế phần mềm. Trong bài báo này chúng tôi sẽ xây dựng và thiết kế mô hình giải các bài toán hồi quy theo các mẫu thiết kế mà Gamma đã đề xuất. Từ đó có một cái nhìn sâu sắc hơn một số mẫu thiết kế, cũng như tìm hiểu một số tính năng mới của ngôn ngữ C# làm cho dễ dàng hơn trong thiết kế phần mềm theo hướng đối tượng. Từ khóa: Các mẫu thiết kế, mẫu thiết kế chiến lược, ngôn ngữ mô hình hóa thống nhất, bài toán hồi quy tuyến tính, bài toán hồi quy phi tuyến, khách hàng GIỚI THIỆU* Trong công nghệ phần mềm, một mẫu thiết kế (design pattern) là một giải pháp tổng thể cho các vấn đề chung trong thiết kế phần mềm. Một mẫu thiết kế không phải là một thiết kế hoàn thiện để mà có thể được chuyển đổi trực tiếp thành mã, nó chỉ là một khung sườn mô tả cách giải quyết một vấn đề mà có thể được dùng lại trong nhiều tình huống khác nhau. Các mẫu thiết kế hướng đối tượng thường cho thấy mối quan hệ và sự tương tác giữa các lớp hay các đối tượng, mà không cần chỉ rõ các lớp hay đối tượng của từng ứng dụng cụ thể [1]. Các mẫu thiết kế có thể giúp tăng tốc quá trình phát triển phần mềm bằng cách cung cấp các mẫu hình phát triển đã được chứng thực và kiểm chứng. Nó cung cấp các giải pháp chung, được viết tài liệu dưới một định dạng mà không gắn liền với một vấn đề cụ thể nào. Các mẫu thiết kế cho phép các nhà phát triển giao tiếp với nhau dùng các tên dễ hiểu được dùng rộng rãi để đặt cho các đối tượng tương tác của phần mềm [4, 5]. Mục đích các công việc của chúng tôi ở đây là xây dựng và thiết kế mô hình giải một số bài toán hồi quy theo mẫu thiết kế mà Gamma đã đề xuất. Từ đó có một cái nhìn sâu sắc hơn về một số mẫu thiết kế có thể được * Tel: 0915 564 249; Email: nmductn@yahoo.com thực hiện trong C#, và tìm hiểu xem các tính năng mới của ngôn ngữ trong thực tế, làm cho nó dễ dàng hơn trong thiết kế phần mềm theo hướng đối tượng. Sau phần giới thiệu, phần 2 sẽ xem xét mẫu thiết kế Chiến lược (Strategy) do Gamma và cộng sự đã đề xuất [1]; Phần 3 sẽ nêu ra một số bài toán hồi quy được quan tâm; Phần 4 là một đề xuất mới về việc xây dựng và thiết kế một mô hình giải các bài toán hồi quy theo mẫu thiết kế; Cuối cùng phần 5 sẽ bao gồm một số nhận xét, kết luận và các công việc trong tương lai. MẪU THIẾT KẾ CHIẾN LƯỢC (STRATEGY PATTERN): Mẫu Strategy được định nghĩa là một họ các thuật toán, đóng gói các thuật toán liên quan và làm chúng hoán đổi cho nhau, điều này cho phép lựa chọn các thuật toán thay đổi độc lập với khách hàng sử dụng nó và thay đổi theo thời gian. Việc xây dựng các mẫu Strategy là để đóng gói một số lượng chiến lược trong một mô-đun duy nhất và cung cấp một giao diện đơn giản cho phép các khách hàng lựa chọn giữa các chiến lược [1]. Cấu trúc của mẫu Strategy như trên hình 1, trong đó: Strategy: Định nghĩa giao diện (hay lớp trừu tượng) cho tất cả các lớp thể hiện giải thuật. Nguyễn Mạnh Đức Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 129 - 135 130 Trong quá trình khởi tạo đối tượng để có thể thêm dữ liệu từ trong Context. ConcreteStrategy: Là các hiện thực của giao diện Strategy để thể hiện một giải thuật cụ thể. Context: Tại thời điểm biên dịch chỉ sử dụng đối tượng kiểu Strategy khi xác định giải thuật cho vấn đề cần xử lý; Tại thời điểm thực thi được cung cấp một đối tượng giải thuật cụ thể thay thế cho đối tượng Strategy. Mẫu Strategy có thể được áp dụng trong những trường hợp sau [1]: Nhiều lớp liên quan chỉ khác nhau ở cách xử lý yêu cầu. Với một lựa chọn trong những cách xử lý theo mẫu Strategy giúp ta thực hiện trách nhiệm của một lớp. Có nhiều cách thực hiện cùng một thuật toán. Phải cho khách hàng khả năng lựa chọn cách ưu việt nhất trong sử dụng tài nguyên và thời gian. Nên dùng Strategy khi các thuật toán này được thể hiện như môt cơ cấu lớp của các thuật toán. Thuật toán cần phải được che dấu cả về dữ liệu và cấu trúc đối với các Client. Dùng Strategy để thay thế việc công khai hoá những cấu trúc dữ liệu phức tạp, đặc thù cho thuật toán. Khách hàng định nghĩa nhiều cách xử lý khác nhau và những cách xử lý này có thể coi như các câu lệnh rẽ nhánh (if- then- elseif, switch) trong phương thức, thay vì dùng các cấu trúc điều kiện ta sẽ dùng các lớp Strategy cài đặt riêng cho từng nhánh. Trong [6] chúng tôi đã cài đặt Strategy Pattern bằng ngôn ngữ C# [2, 3, 7]. Các đoạn mã ở đó đã minh chứng cho mô hình Strategy, sự đóng gói chức năng hình thức của một đối tượng được thực hiện trong C# dựa vào cấu trúc của mẫu Strategy như trong hình 1. Trong các phần sau chúng tôi sẽ đề xuất xây dựng và thiết kế mô hình áp dụng giải quyết bài toán hồi quy theo Strategy Pattern. BÀI TOÁN HỒI QUY Các bài toán hồi quy được sử dụng trong nhiều lĩnh vực. Sau đây chúng ta xét một dạng bài toán hồi quy tuyến tính và phi tuyến tính hay được sử dụng nhất. Bài toán hồi quy tuyến tính Mô hình hồi quy tuyến tính bội có dạng như sau [8]: iinn2i21i10i uXXXY   (1) trong đó: ui là các biến ngẫu nhiên không tương quan có kỳ vọng bằng 0 và phương sai không đổi 2; 0, 1, 2, ... , n là các tham số cần ước lượng. Các ước lượng n10 ˆ,...,ˆ,ˆ  của 0, 1, 2, ..., n được xác định bằng phương pháp bình phương tối thiểu. Ngoài việc ước lượng, nếu muốn tìm khoảng tin cậy của các tham số hay tiến hành kiểm định, ta phải giả thiết thêm các biến ngẫu nhiên có phân phối chuẩn ui  N(0, 2) [8]. Hình 1: Cấu trúc mẫu Strategy [1] Nguyễn Mạnh Đức Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 129 - 135 131 Một số bài toán hồi quy phi tuyến Sau đây ta xét một số dạng hồi quy phi tuyến điển hình rất hay được sử dụng trong khoa học kỹ thuật, kinh tế-xã hội, khoa học dự báo, sinh học... Các dạng bài toán này đều có thể đưa được về dạng hồi quy tuyến tính [8, 9]. Bài toán hồi quy phi tuyến dạng mũ (hàm Cobb Douglas) Mô hình hồi quy mũ có dạng : yi = b0 Xi1b1 Xi2b2 Xinbn (2) Để xác định các tham số bi (i = 0,1, ..., n) từ các số liệu thu thập, ta chuyển về dạng bài toán hồi quy bội bằng cách logarit tự nhiên hai vế (2), đặt Y = lnyi, b’ = lnb0, Xi = lnxi (i = 1 .. n), thì được bài toán tuyến tính bội Y = b’ + b1X1 + b2X2 + ... + bnXn. Bài toán Cobb Douglas tổng quát Mô hình Cobb Douglas tổng quát có dạng: )()( 1 txaetY m i i bt i    (3) Trong đó : a, b, i > 0, i = 1 .. m t là biến thời gian (t = 1, 2, ...); xi(t) là các nhân tố sản xuất; Y(t) là các kết quả sản xuất. Để xác định các hệ số a, b, i, ta logarit tự nhiên hai vế (3) và biến đổi như sau: lnY = lna + bt + 1lnx1 + ... + m-1lnxm-1 + mlnxm = lna + bt + 1lnx1 + ... + m-1lnxm-1 + (1- 1 - ... - m-1)lnxm. Hay: lnY - lnxm = lna + bt + 1(lnx1 - lnxm) + 1(lnx2 - lnxm) +...+ m-1(lnxm-1 - lnxm)  ln(Y/xm) = lna + bt + 1ln(x1/xm) + 2ln(x2/xm) + ... + m-1ln(xm-1/xm). Đặt: ln(Y/xm) = g; lna = k; ln(xi/xm) = Zi, ta sẽ có bài toán hồi quy tuyến tính: g = k + bt + z11 + z22 + ... + zm-1m-1. Hồi quy đa thức Hàm hồi quy đa thức có dạng: y = a0 + a1t1 + a2t2 + ... + antn (4) Trong đó các ai (i = 0, 1 ... n ) là các hằng số cần xác định, t là biến thời gian. Để xác định các ai (i=0 ... n) từ số liệu thực nghiệm ta đưa (4) về bài toán hồi quy tuyến tính bằng phép đổi biến: x1 = t, x2 = t2 , ... , xn = tn, từ đó ta có được bài toán hồi quy tuyến tính bội. Nhiều bài toán hồi quy phi tuyến khác có thể được giải bằng cách chuyển về bài toán hồi quy tuyến tính mà vẫn đảm bảo tính chính xác [8]. Phương pháp giải một số bài toán hồi quy phi tuyến Trong phần trên chúng ta đã đưa ra một số dạng trong lớp bài toán hồi quy phi tuyến, để giải các bài toán đó chúng ta có thể chuyển chúng về dạng bài toán hồi quy tuyến tính, cụ thể thực hiện các bước như sau: Tuyến tính hoá bài toán phi tuyến: Chuyển dữ liệu của bài toán phi tuyến về dạng áp dụng được cho bài toán tuyến tính. Giải bài toán hồi quy tuyến tính với dữ liệu của bài toán phi tuyến đã được chuyển đổi phù hợp. Trả lại các thông số cho bài toán hồi quy phi tuyến. Trong phần tiếp theo chúng tôi sẽ đề xuất mô hình giải các bài toán hồi quy như đã trình bày ở trên theo mẫu thiết kế Strategy. THIÊT KẾ MÔ HÌNH GIẢI MỘT SỐ BÀI TOÁN HỒI QUY THEO MẪU THIẾT KẾ Mô hình giải các bài toán hồi quy theo mẫu Chiến lược trong ngôn ngữ C# được chúng tôi thiết kế như trên hình vẽ 2. Trong đó: IRegression là giao diện (interface) xác định các dịch vụ phục vụ cho việc giải các bài toán hồi quy tuyến tính theo yêu cầu. Linear_Regression là lớp thực thi của giao diện IRegression, các phương thức đã khai báo trong IRegression sẽ được thực hiện trong lớp này. NonLine_Regressioni (ở đây i = 1 .. 3): là các lớp con, được kế thừa từ Linear_Regression, mỗi lớp con này sẽ thực    m i i 1 1 Nguyễn Mạnh Đức Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 129 - 135 132 hiện việc giải một bài toán hồi quy phi tuyến tính theo yêu cầu. Context: Tại thời điểm biên dịch chỉ sử dụng đối tượng kiểu IRegression xác định giải thuật cho vấn đề cần giải bài toán hồi quy; Tại thời điểm thực thi được cung cấp một đối tượng giải thuật cụ thể thay thế cho đối tượng IRegression để giải một bài toán hồi quy phi tuyến cụ thể. Các phương thức trong giao diện được khai báo như sau: interface IRegression { void INPUT_DATA(); void DISPLAY(); void EDIT_DATA(); void GET_DATA(); void TRANSLATE(); void SLOVE(); void TEST(); } Phần thân của chúng sẽ được định nghĩa trong lớp Linear_Regression, trong đó: void INPUT_DATA(): Nhập dữ liệu cho bài toán; void DISPLAY(): Hiển thị các thông cũng như kết quả xử lý; void EDIT_DATA(): Sửa dữ liệu khi cần; void GET_DATA(): Lấy dữ liệu từ tệp cho bài toán; void TRANSLATE(): Chuyển đổi dữ liệu cho bài toán; void SLOVE(): Giải bài toán hồi quy tuyến tính; void TEST(): Kiểm định các giả thuyết Việc thực thi các phương thức của interface IRegression được thực hiện trong lớp Linear_Regression để giải bài toán hồi quy tuyến tính được xác định như sau: class Linear_Regression : IRegression Hình 2: Biểu đồ UML của mô hình bài toán Nguyễn Mạnh Đức Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 129 - 135 133 { public void INPUT_DATA() { ...//Nhập dữ liệu } public void DISPLAY() { ...//Hiển thị t.tin } public void EDIT_DATA() { ... //Sửa dữ liệu } public void GET_DATA() { ...//Đọc dữ liệu từ tệp } public virtual void TRANSLATE() { ...//Chuyển dữ liệu } public virtual void SLOVE() { ...//Giải bài toán HQTT } public virtual void TEST() { ...//Kiểm thử bài toán } } Cần chú ý rằng các phương thức TRANSLATE(), SLOVE(), TEST() phải là ảo (virtual) vì chúng cần phải được ghi đè trong các lớp hậu duệ (kế thừa) của lớp Linear_Regression để xử lý cho các bài toán hồi quy phi tuyến. Các lớp NonLine_Regressioni (i=1..3) được cài đặt như sau: class NonLinear_Regressioni : Linear_Regression { public override void TRANSLATE() {...} public override void TEST() {...} public override void SLOVE() { TRANSLATE(); base.SLOVE(); } } Trong đó phương thức TRANSLATE()để biến đổi dữ liệu bài toán phi tuyến thành dữ liệu cho bài toán tuyến tính, TEST() để kiểm thử cho bài toán, phương thức SLOVE() sẽ gọi thức TRANSLATE()để lấy dữ liêu phù hợp cho bài toán tuyến tính, rồi gọi phương thức SLOVE() ở lớp cơ sở của chúng. Lớp NonLine_Regression1 để giải bài toán hồi quy dạng mũ, lớp NonLine_Regression2 để giải bài toán Cobb Douglas tổng quát, lớp NonLine_Regression3 để giải bài toán hồi quy đa thức. Trong các lớp này các tên của các phương thức là giống nhau, nhưng nội dung của chúng là khác nhau tùy thuộc vào mỗi bài toán. Lớp context được cài đặt như sau: class Context { IRegression ihq; public Context(IRegression ihq) { this.ihq = ihq; } public void ContextInterface() { this.ihq.GET_DATA(); this.ihq.SLOVE(); this.ihq.TEST(); } ...//các thành phần khác } Khi đó một lớp Client với hàm Main có thể dễ dàng gọi các đối tượng cần thiết cho Nguyễn Mạnh Đức Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 129 - 135 134 từng loại bài toán theo mẫu thiết kế Strategy như sau: class Client { static void Main(string[] args) { Context hqtt = new Context(new Linear_Regression()); hqtt.ContextInterface(); Context hqpt1 = new Context(new NonLinear_Regression1()); hqpt1.ContextInterface(); Context hqpt2 = new Context(new NonLinear_Regression2()); hqpt2.ContextInterface(); Context hqpt3 = new Context(new NonLinear_Regression3()); hqpt3.ContextInterface(); } } Mô hình được thiết kế như vậy có ưu điểm: Các khách hàng có thể gọi tới bài toán cần thiết thông qua các phương thức của lớp context, mà không cần biết tới các chi tiết cụ thể của chúng; Việc thay đổi các chi tiết của giải thuật giải các bài toán được thực hiện theo yêu cầu của các lớp con cụ thể, điều đó sẽ làm dễ dàng cho việc mở rộng phát triển các bài toán khác mà không ảnh hưởng tới các module đã có của chương trình Chúng tôi đã cài đặt chương trình thử nghiệm cho mô hình đã đề xuất trên, bước đầu đáp ứng được một số các yêu cầu đã đặt ra và cho các kết quả tính toán chính xác. Chương trình có thể được mở rộng dễ dàng và thuận lợi cho tích hợp vào các hệ thống khác. NHẬN XÉT VÀ KẾT LUẬN Trong công nghệ phần mềm, mẫu thiết kế là một giải pháp tổng thể cho các vấn đề chung trong thiết kế phần mềm. Ý tưởng sâu xa của các mẫu thiết kế là để tiết kiệm tốt các giải pháp thiết kế hướng đối tượng và việc tái sử dụng chúng để giải quyết các vấn đề tương tự trong những ngữ cảnh khác nhau. Trong bài báo này, trên cơ sở của các nguyên lý thiết kề phần mềm theo hướng đối tượng và các mẫu thiết kế, chúng tôi đã đề xuất thiết kế mô hình giải các bài toán hồi quy. Việc xây dựng mô hình tính toán như vậy sẽ dễ dàng mở rộng và phát triển mô hình, an toàn, nâng cao khả năng sử dụng lại, thuận lợi cho việc tích hợp các module chương trình vào các hệ thống phần mềm khác... Mô hình giải các bài toán hồi quy mà chúng tôi đã xây dựng và thiết kế có các đặc điểm: Tuân theo các nguyên lý thiết kế hướng đối tượng dựa trên mẫu Strategy; Sự kế thừa giữa các lớp được tận dụng tối đa phục vụ cho việc tái sử dụng các module chương trình; Quan hệ giữa các lớp ở mức tổng quát, thuận lợi cho việc phát triển mở rộng của mô hình để giải các bài toán hồi quy khác Trong tương lai chúng tôi sẽ xem xét, thực hiện xây dựng và phát triển mô hình tính toán kết hợp với các mẫu thiết kế khác để được một hệ thống đa dụng và tốt hơn; Nghiên cứu về việc làm mịn các mẫu thiết kế; Áp dụng các mẫu và kết hợp chúng để giải quyết các bài toán khác trong thực tế. TÀI LIỆU THAM KHẢO 1. Gamma E., et. al, Elements of Reusable Object- Oriented Software, Addison-Wesley. The PDF conversion was made in February 2003. 2. Liberty J., Programming C#, 2nd Edition, O’Reilly, ISBN: 0-596-00309-9, 2002. 3. MSDN, C# Language specification 17. Attributes, Microsoft Corporation 2004. 4. Mathias Bartoll, Nori Ahari, Oliver C.Moldez, Design patterns in C#, Mälardalen University Västerås, Sweden. 2004. Nguyễn Mạnh Đức Tạp chí KHOA HỌC & CÔNG NGHỆ 122(08): 129 - 135 135 5. Sherif M. Yacoub, H.H. Ammar, Pattern -Oriented Analysis and Design: Composing Patterns to Design Software Systems, Addison Wesley 2003. 6. Nguyen Manh Duc (2012), “Building some design patterns in C#” Journal of science and technology, Thainguyen University, volume 90 (02), p. 77-86. 7. Phạm Hữu Khang, Trần Tiến Dũng, C# 2005 Lập trình Hướng đối tượng, Nhà xuất bản Lao động xã hội, 2008. 8. Nguyễn Cao Văn, Trần Thái Ninh, Lý thuyết xác xuất và thống kê, Nhà xuất bản Khoa học và kỹ thuật, 1996. 9. Nguyễn Mạnh Đức, Giáo trình tin học ứng dụng, Nhà xuất bản Nông nghiệp, 2000. SUMMARY APPLYING DESIGN PATTERNS TO CONSTRUCT MODEL SOLVE SOME REGRESSION PROBLEM Nguyen Manh Duc* College of Education - TNU The problem of regression is widely used in scientific, technical, socio-economic... handle tasks such as trend analysis of the evolution of the phenomenons, computational optimization, forecasting... In software engineering, design patterns as a general solution to the common problems in software design. In this article we will build and design the model solve regression problems based on the designs that Gamma has proposed. From there take a deeper look at some of the designs, as well as learn the new features of C# language makes it easier to design object- oriented software. Key words: Design Patterns, Strategy pattern, UML, Linear Regression Problem, NonLinear Regression Problem, Client Ngày nhận bài:06/5/2014; Ngày phản biện:20/5/2014; Ngày duyệt đăng: 25/8/2014 Phản biện khoa học: TS. Vũ Vinh Quang – Trường Đại học Công nghệ Thông tin & Truyền thông - ĐHTN * Tel: 0915 564 249; Email: nmductn@yahoo.com