Đề tài Thư viện mã nguồn mở cho bài toán dự báo- An open source library for prediction problems

THƯ VIỆN MÃ NGUỒN MỞ CHO BÀI TOÁN DỰ BÁO AN OPEN SOURCE LIBRARY FOR PREDICTION PROBLEMS Dương Ngọc Hiếu, Võ Hoàng Tam, Nguyễn Thành Thi (*) Khoa Khoa học & Kỹ thuật Máy tính, ĐH Bách khoa Tp. Hồ Chí Minh (*) Bộ môn Thông tin Địa lý Ứng dụng, ĐH Nông – Lâm Tp. Hồ Chí Minh {dnhieu, vhtam}@cse.hcmut.edu.vn, nnthi@hcmuaf.edu.vn BÁN TÓM TẮT Khai phá dữ liệu hiện đang là lãnh vực nghiên cứu rất phát triển. Cho đến thời điểm hiện nay đã có một số thư viện mã nguốn được hiện thực để đáp ứng cho các bài toán khai phá dữ liệu. Tuy nhiên hầu như chưa có một thư viên mã nguồn mở nào chuyên biệt cho lớp bài toán dự báo. Bài báo sẽ giới thiệu về thư viện mã nguồn mở cho bài toán dự báo với những giải thuật tiên tiến hiện nay như Artificial Neural Network (ANN), Support Vector Regression (SVR), Standard Addictive Model (SAM). ABSTRACT Datamining has recently been an emerging research trend. For the time being, there have been some open source libraries implemented to solve datamining problems. However, there is no library specialized in predicting technique. In this paper, we implement an open source library for solving prediction problems using some advanced algorithm such as: Artificial Neural Network (ANN), Support Vector Regression (SVR), Standard Addictive Model (SAM). 1. GIỚI THIỆU Con người luôn luôn quan tâm đến tương lai. Từ xa xưa các nhà tiên tri luôn giữ một vị trí quan trọng trong cộng đồng. Khi văn minh nhân loại phát triển đã làm gia tăng các mối quan hệ phức tạp vốn có trong cuộc sống. Do đó con người cần có cái "nhìn về tương lai" của họ. Ngày nay, tất cả các cơ quan Chính phủ, các tổ chức lợi nhuận, phi lợi nhuận cũng như những công ty trong lĩnh vực kinh doanh và các cá nhân đều có nhu cầu dự báo về sự kiện tương lai nhằm phục vụ cho công việc của mình: kế hoạch phát triển công ty, tỉ lệ lợi nhuận trong kinh doanh… Mặc dù có nhiều kỹ thuật dự báo đã phát triển trong thế kỷ thứ 19, tuy nhiên dự báo có ảnh hưởng mạnh mẽ mới đây chỉ vào lúc công nghệ thông tin đang phát triển nhanh chóng. Bởi vì việc mô phỏng những phương pháp dự báo rất cần sự hỗ trợ của máy tính. Trong quá khứ, nhiều phần mềm được thiết kế đặc biệt cho những phương pháp phân tích dự báo khác nhau. Ngoài ra những phần mềm thống kê vận hành trong những máy tính thông thường cũng đã đề cập đến nhiều kỹ thuật dự báo. Với sự phát triển của hệ thống máy tính cá nhân, các kỹ thuật dự báo hiện đại được triển khai thực hiện một cách nhanh chóng dễ dàng. Một trong những kỹ thuật dự báo hiện đại đó là data mining. Có rất nhiều phương pháp data mining sử dụng để dự báo như: neural network, support vetor regression, perceptron regression, … Các phương pháp dự báo này có những ưu và nhược điểm khác nhau tùy vào vấn đề cần giải quyết. Do đó khi gặp phải một bài toán cụ thể, ta phải dựa vào tính chất của bài toán để lựa chọn phương pháp thích hợp. Ngày nay đã xuất hiện khá nhiều thư viện data mining mã nguốn mở như Xelopes, Weka, … đã hiện thực nhiều giải thuật khác nhau đáp ứng cho các bài toán data mining. Tuy nhiên hầu như chưa có một thư viên mã nguồn mở nào chuyên biệt cho lớp bài toán dự báo. Bài báo sẽ giới thiệu về thư viện mã nguồn mở cho bài toán dự báo với những giải thuật tiên tiến hiện nay như ANN, SVR, SAM. Phần còn lại của bài báo gồm các nội dung sau. Phần 2 trình bày tổng quan về bài toán dự báo. Phần 3 điểm qua các giải thuật dự báo đã được hiện thực trong thư viện mã nguồn mở. Trong phần 4, chúng tôi mô tả sơ lược kiến trúc của thư viện mã nguốn mở. Các so sánh thực nghiệm được nêu ra trong phần 5. Phần 6 đúc kết và vạch ra hướng phát triển trong tương lai. 2. TỔNG QUAN VỀ BÀI TOÁN DỰ BÁO Trong lãnh vực dự báo, thường được chia ra làm hai hướng: 2.1. Phương pháp định tính Phương pháp định tính (đôi khi được gọi là phương pháp chuyên gia hay phương pháp phân tích cơ sở) thường được sử dụng khi những dữ liệu lịch sử không sẵn có hay có nhưng không đầy đủ, hay những đối tượng dự báo bị ảnh hưởng bởi những nhân tố không thể lượng hoá đuợc: sự thay đổi tiến bộ kỹ thuật, ảnh hưởng của tác động môi trường…. Những phương pháp này bao gồm việc sử dụng những đánh giá, những kinh nghiệm của một hay nhiều chuyên gia trong lĩnh vực liên quan. Thủ tục dự báo định tính thông thường được trình bày dưới dạng giải thích (exploratory) hay chuẩn tắc (normaltive). + Phương pháp giải thích sẽ sử dụng những thông tin quá khứ và hiện tại để hướng tới tương lai thông qua những kịch bản có thể. Từ đó các chuyên gia có thể cung cấp những dự báo ”về điều gì có thể diễn ra và khi nào điều đó có thể diễn ra”. Những ước lượng chi phí nhằm đạt được mục tiêu thường được áp dụng dưới dạng dự báo giải thích. + Phương pháp chuẩn tắc sẽ căn cứ những mục tiêu tương lai và kế đó sẽ quy ngược trở lại hiện tại để tìm hiểu và đánh giá rằng những nguồn lực nào hiện có, những giới hạn cần loại bỏ hay khắc phục. Thông thường những đột phá khoa học nào đó (ví dụ như là những đột phá đã phát triển bởi chương trình không gian NASA) sẽ là những sản phẩm phụ để đạt được một vài mục tiêu dài hạn khác trong tương lai. Ưu Điểm của phương pháp dự báo định tính: + Sử dụng tối đa những thông tin có được (bao gồm những thông tin có thể lượng hoá và không thể lượng hoá) để tiến hành dự báo. Khuyết điểm của phương pháp này: + Không có một phương pháp hệ thống để cải thiện độ chính xác dự báo. + Có thể làm sai lệch kết quả dự báo xuất phát từ đánh giá chủ quan của các chuyên gia dự báo. 2.2. Phương pháp định lượng Ngược với phương pháp định tính, phương pháp định lượng sử dụng những dữ liệu quá khứ theo thời gian. Nói cách khác, dựa trên những dữ liệu lịch sử để phát hiện chiều hướng vận động của đối tượng phù hợp với một mô hình toán học nào đó và đồng thời sử dụng mô hình này là mô hình ước lượng. Tiếp cận định lượng dựa trên giả định rằng giá trị tương lai của biến số dự báo sẽ phụ thuộc vào xu thế vận động của đối tượng đó trong quá khứ. Có các loại phương pháp định lượng như sau: + Phương pháp chuỗi thời gian dựa trên phân tích chuỗi quan sát của một biến duy nhất theo biến số độc lập là thời gian. Tần suất có thể là ngày, tháng, quý và năm. Những biến số kinh tế quan tâm có thể là biến vĩ mô hay vi mô. Những phạm vi quan sát có thể là hãng, tỉnh, hay cả nền kinh tế. Giả định chủ yếu là biến số kinh tế dự báo sẽ giữ nguyên chiều hướng phát triển đã diễn ra trong quá khứ và hiện tại. + Mô hình nhân quả giả định biến số dự báo có thể được giải thích bởi hành vi của những biến số kinh tế khác (biến số độc lập). Ví dụ: doanh số có thể giải thích phụ thuộc vào chi phí quảng cáo, thu nhập của khách hàng, giá sản phẩm, đối thủ cạnh tranh và những nhân tố ảnh hưởng khác. Mục đích của mô hình nhân quả là tìm ra những hình thức (mô hình toán) mô tả mối quan hệ giữa tất cả các biến số và sử dụng nó để dự báo biến số kinh tế đang quan tâm (biến phụ thuộc). + Phương pháp phân loại và nhận diện mẫu sẽ cố gắng phân loại tập dữ liệu thành nhiều loại, nhận diện hướng dịch chuyển của dữ liệu trong tương lai. + Phương pháp lai là sự pha trộn của các phương pháp trên. Một trong những phương pháp chuỗi thời gian thường được ưa chuộng nhất là phương pháp mạng neuron. 3. CÁC GIẢI THUẬT ĐƯỢC ÁP DỤNG 3.1. Giải thuật ANN Mô hình mạng truyền thống MLP Trong nhiều năm qua, mô hình mạng neuron đa tầng (Multi Layer Perceptron) được ứng dụng rộng rãi trong nhiều lĩnh vực như: phân tích tài chính, chẩn đoán bệnh, dự báo thời tiết, v.v... Đặc biệt trong vài năm trở lại đây, có rất nhiều các nghiên cứu về ứng dụng mạng neuron trong dự báo giá cả của các mặt hàng trên thị trường. Trong mô hình dự báo dựa trên mô hình mạng neuron: Tập các lớp được phân loại: C ={ }Mωωω ,...,, 21 Tập dữ liệu mẫu cho quá trình huấn luyện là tập hợp các bộ giá trị gồm (x,d) gồm: - Vector đặt trưng x = (x1,x2,..xn) - Giá trị của loại dữ liệu cần dự báo d Với tập trọng số w , mạng neuron sẽ đưa ra ngõ ra d(x,w) = ƒ(uj) uj: là hàm tổng tuyến tính của vector trọng số và ngõ ra của các neuron ƒ(uj): là hàm hoạt tính, trong đó hàm sigmoid )exp(1 1 juβ−+ được sử dụng nhiều nhất . Có nhiều phương pháp để đánh giá lỗi, trong đó hàm “mean squared error” được sử dụng nhiều nhất Min ( )∑∑ = = − N i K j ijij XdXy 1 2 1 )()W,( Giải thuật học mạng là giải thuật backpropagation. Mô hình mạng neuron kết hợp với lý thuyết mờ: Recurrent Fuzzy Neural Network (RFNN) Để cải tiến hiệu suất của giải thuật ANN, một phương pháp được ưa chuộng đó là kết hợp ANN và lý thuyết mờ. có nhiều cách kết hợp một trong những cách phổ biến đó là dựa vào mô hình dự báo mờ, xây dựng lại một mô hình mới gồm 4 lớp: Lớp 1: Là lớp nhập gồm N dữ liệu nhập (input). Lớp 2: Gọi là lớp các hàm thành viên. Các nút trong lớp này thực hiện việc mờ hoá. Lớp này dùng để tính giá trị hàm thành viên theo hàm phân phối Gauss. Số nút trong lớp 2 là N x M, trong đó M là số luật mờ (số nút của lớp 3) Lớp 3: Lớp các luật mờ. Các nút trong lớp này tạo thành cơ sở luật mờ (Fuzzy rule base) gồm M nút. Liên kết giữa lớp 2 và lớp 3 biểu diễn giả thiết của luật mờ. Liên kết giữa lớp 3 và lớp 4 biểu diễn kết luận của luật mờ. Lớp 4: Lớp xuất gồm P nút có chức năng giải mờ. Giải thuật học cho mô hình mạng RFNN cũng là giải thuật backpropagation Mô hình mạng neural kết hợp với giải thuật gen Có nhiều cách kết hợp giải thuật gen với mạng neuron. Tuy nhiên phương pháp sau đây được xem là hữu hiệu nhất: - Xem mạng neuron như một cá thể. - Quần thể bao gồm nhiều cá thể mạng neuron. - Trước khi chọn ra cá thể tốt thực hiện các phép toán gen để sinh ra tập quần thể mới, các cá thể tự tối ưu bằng phương pháp backpropation. 3.2. Giải thuật Support vector regression (SVR) Cho một tập huấn luyện {(x1, y1), (x2, y2)…., (xl, yl)} với x Є Rn, y Є R. Mục đích của phương pháp hồi quy ε-SV [2] là tìm một hàm f(x) có độ lệch lớn nhất là ε so với các giá trị đích yi của tất cả các mẫu huấn luyện. Tuy nhiên ta có thể nới lỏng điều kiện này bằng cách đưa thêm sai số vào thông qua gia số ξ (xem hình 1.) Hình 1. Xấp xỉ hàm theo phương pháp ε-SV Để đơn giản ta có thể chọn hàm f có dạng tuyến tính như sau: f(x) = (w.x) + b. Bài toán có thể được phát biểu như sau: Cực tiểu hóa giá trị: ∑ = ++ l i iiCw 1 *2 )(|||| 2 1 ξξ Với điều kiện: 0, ).( ).( * * ≥ +≤−+ +≤−− ii iii iii ybxw bxwy ξξ ξε ξε Chuyển bài toán tối ưu ở trên sang bài toán đối ngẫu (dual problem), áp dụng phương pháp Larange: Để L đạt được cực trị thì các đạo hàm riêng phải = 0: Do đó: bxxxf l i iii +−= ∑ =1 * ).)(()( αα 3.3. Giải thuật SAM SAM là hệ thống gồm m luật mờ hoạt động theo cơ chế song song. Các luật mờ có dạng: “NẾU tập các điều kiện được thỏa mãn THÌ tập các kết quả sẽ xảy ra”. Không mất tính tổng quát khi ta phân rã một hệ thống đa ngõ nhập, đa ngõ xuất (MIMO) thành một nhóm các hệ thống đa ngõ nhập, đơn ngõ xuất (MISO). Luật mờ MISO có dạng: NẾU (x1 là Ai1 VÀ … VÀ xd là Aid) THÌ (y là Bi). Hình 2. Cơ chế hoạt động của SAM. Các luật mờ của SAM được xây dựng dựa trên giải thuật phân lớp theo cơ chế học không giám sát. Hệ mờ sẽ xấp xỉ tốt hơn nếu thực hiện quá trình tối ưu hệ luật và điều chỉnh các thông số hệ luật theo cơ chế học giám sát. Các thông số hệ luật sẽ được điều chỉnh bằng luật học sai số nhỏ nhất. Trong SAM, ứng với mỗi giá trị đầu vào x = x0, luật thứ j sẽ kích hoạt và cho kết quả là tập mờ Bj’ được xây dựng dựa theo mức độ thỏa mãn vế trái và tập mờ Bj của vế phải theo quy tắc PROD: ( ) ( ) (yB.µxAµyB'µ = ) Tập mờ ngõ ra B được xây dựng theo quy tắc SUM các tập mờ Bj’: ∑== m j ' jΒΒ 1 Tập B được giải mờ để nhận được một giá trị rõ duy nhất: ( ) jV m j (x).j.ajw j.cjV m j (x).j.ajw BCentroidF(x) ∑= ∑=== 1 1 4. HIỆN THỰC THƯ VIỆN MÃ NGUỐN MỞ Mục đích của thư viện mã nguốn mở là cho phép người dùng có thể xây dựng những ứng dụng dự báo dựa trên thư viện đã có sẵn. Ngoài ra khi cần, có thể phát triển thêm giải thuật để gắn vào thư viện có sẵn. Kiến trúc hiện thực thư viện (hình 3) gồm hai phần chính: + Giao diện người dùng: cho phép người dùng tương tác với phần mềm dự báo. + Giải thuật: tập những giải thuật dự báo như ANN, SVR, SAM. Một vấn đề đặt ra là khi người dùng cần xây dựng ứng dụng với dữ liệu đang có, làm sao thư viện có thể đọc hiểu được những dữ liệu này. Để giải quyết vấn đề này, các giải thuật chỉ chấp nhận một định dạng dữ liệu nhập duy nhất. Như vậy khi người sử dụng thư viện muốn phát triển ứng dụng dự báo, họ phải override lại lớp tiền xử lý dữ liệu để chuyển dữ liệu hiện có sang định dạng qui định (theo định dạng XML). Hình 3. Kiến trúc thư viện mã nguồn mở cho bài toán dự báo. Định dạng của dữ liệu sau khi đã được xử lý bao gồm 2 phần: - Phần thứ nhất là cấu trúc của bộ dữ liệu. Cấu trúc này được đọc hiểu bởi những giải thuật dự báo đã hiện thực. - Phần thứ hai là dữ liệu dùng để học cho các giải thuật dự báo Dưới đây là giao diện người sử dụng của thư viện đã được xây dựng. Hình 4: Giao diện mở đầu. Người dùng có thể lựa chọn các các giải thuật dự báo khác nhau như: neural network, SAM fuzzy system, SVM hay mô hình hồi quy tuyến tính ARIMA (xem hình 4.). Hình 5. Giao diện mô hình neural network. 5. KẾT QUẢ SO SÁNH THỰC NGHIỆM Để kiểm tra thư viện đã xây dựng chúng tôi sử dụng tập dữ liệu giá của vàng, cà phê, … của Việt Nam để đo đạc và kiểm nghiệm. Tập dữ liệu này được thu thập từ năm 1997 cho đến 2007 (trung binh một năm sẽ có 365 hàng dữ liệu). Chương trình được kiểm tra trên hệ thống máy tinh đơn CPU P4 1.4GHz, RAM 769. Đây là một số kết quả đo đạc được khi thực thi dự báo bằng giải thuật SAM. STT Số luật mờ Trung bình lỗi đầu Trung bình lỗi sau Thời gian 1 499 0.07013 0.00450 05 giờ 29 phút 2 399 0.10924 0.00457 06 giờ 56 phút 3 160 0.12512 0.00984 08 giờ 48 phút Bảng 1 Đánh giá theo số luật mờ. ST T Hàm Trung bình lỗi đầu Trung bình lỗi sau Thời gian 1 Cauchy 0.10924 0.00457 06 giờ 56 phút 2 Gaussian 0.10752 0.00410 07 giờ 05 phút 3 Laplace 0.08828 0.00212 09 giờ 41 phút Bảng 2 Đánh giá theo hàm thành viên. Những thống kê trên mô hình ANN và các hệ lai của ANN có thể tham khảo tại (1). Thực nghiệm cho thấy các phương pháp dự báo hồi quy phi tuyến (ANN, SVM, SAM) có độ chính xác cao và thời gian chạy tương đối nhỏ. Nếu so sánh với mô hình ARIMA trong khoảng thời gian ngắn thì có thể xem là tương đương. Tuy nhiên ARIMA là phương pháp hồi quy tuyến tính nên nếu dữ liệu có sự biến động lên xuống liên tục thì ARIMA sẽ không còn chính xác nữa. Hình 6. So sánh các phương pháp hồi quy phi tuyến và tuyến tính. Trong các giải thuật phi tuyến, có thể thấy SAM cho kết quả dự báo ổn định và hữu hiệu nhất. 6. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Bài báo này trình bày kết quả của đề tài nghiên cứu “Xây dựng thư viện mã nguốn mở cho bài toán dự báo”. Kết quả đạt được cho thấy thư viện này hoàn toàn có thể được sử dụng để dự báo cho các bài toán thực thuộc các lãnh vực khác nhau như môi trường, tài chánh, y tế, … Trong thời gian tới chúng tôi tiến hành xây dựng thêm những phương pháp dự báo khác như mô hình HMME là sự kết hợp của ANN và Hidden Markov Model để tăng hiệu suất khi dự báo những tập dữ liệu có độ biến động lớn. Đồng thời cải tiến các giải thuật đã xây dựng như cải thiện các giải thuật học cho ANN, SAM. TÀI LIỆU THAM KHẢO 1. Dương Ngọc Hiếu , “Ứng dụng mạng neural dự báo giá các sản phẩm trên thị trường”, Luận văn cao học ngành Khoa học Máy tính Khóa 2004. 2. Alex J. Smola, Bernard Scholkopf, “A tutorial on support vector regression”, Statistics and Computing 14: 199-222, 2004. 3. Takagi, T. and Sugeno, M. Fuzzy identification of systems and its application to modeling and control. IEEE Trans. on Systems, Man & Cybernetics 15, 116-132, 1985. 4. Sugeno, M. and Yasukawa, T. A fuzzy-logic- based approach to qualitative modeling. IEEE Trans. on Fuzzy Systems 1, 7-31, 1993. 5. Wang, L.X. Training of fuzzy logic systems using nearest neighborhood clustering. Proc. 2nd IEEE Int'l Conf. on Fuzzy Systems (FUZZ-IEEE ‘93), San Francisco, CA, March 28-April 1, 13- 17, 1993. 6. Yager, R. and Filev, D. Generation of fuzzy rules by mountain clustering. J. of Intelligent and Fuzzy Systems 2, 209-219, 1994. 7. Chiu, S. Fuzzy model identification based on cluster estimation. J. of Intelligent and Fuzzy Systems 2, 267-278, 1994. 8. Ruspini, E.H. Numerical methods for fuzzy clustering. Inform. Sci. 2, 319-350, 1970. 9. Dunn, J. A fuzzy relative of the ISODATA process and its use in detecting compact, well separated clusters. J. of Cybernetics 3, 32-57, 1974. 10. Bezdek, J. Cluster validity with fuzzy sets. J. of Cybernetics 3, 58-71, 1974. 11. Keller, J., Gray, M. and Givens Jr., J. A fuzzy k- nearest neighbor algorithm. IEEE Trans. Syst., Man, Cybern., 15, 580-585, 1985. 12. Chung, F.L. and Lee, T. A fuzzy learning method for membership function estimation and pattern classification. Proc. 3rd IEEE Int'l Conf. on Fuzzy Systems (FUZZ-IEEE ‘94), Orlando, FL, June 26-29, 426-431, 1994. 13. Sun, C.T. and Jang, J.S.R. A neuro-fuzzy classifier and its applications. Proc. 2nd IEEE Int'l Conf. on Fuzzy System (FUZZ-IEEE ‘93), San Francisco, CA, March 28-April 1, 94-98, 1993. 14. Abe, S. and Lan, M.S. A classifier using fuzzy rules extracted directly from numerical data. Proc. 2nd IEEE Int'l Conf. on Fuzzy Systems (FUZZ-IEEE ‘93), San Francisco, CA, March 28-April 1, 1191-1198, 1993. 15. Wang, L.X. and Mendel, J.M. Back-propagation fuzzy system as nonlinear dynamic system identifiers. Proc. 1st IEEE Int'l Conf. on Fuzzy Systems (FUZZ-IEEE ‘92), San Diego, CA, March 8-12, 1409-1418, 1992. 16. Jang, J.S.R. ANFIS: Adaptive-network-based fuzzy inference system. IEEE Trans. Syst., Man, Cybern. 23, 665-685, 1993. 17. Chiu, S. Extracting fuzzy rules for pattern classification by cluster estimation. Proc. 6’th Int. Fuzzy Systems Association Congress (IFSA ‘95), Sao Paulo, Brazil, July 22-28, vol. 2, 273- 276, 1995. 18. Kikuchi, S., Nanda, R., and Perincherry, V. Estimation of trip generation using the fuzzy regression method. Proc. 1994 Annual Meeting of Transportation Research Board, Washington DC, January, 1994. 19. Chiu, S. Selecting input variables for fuzzy models. To appear in J. of Intelligent & Fuzzy Systems, 1996. 20. Fisher, R.A. The use of multiple measurements in taxonomic problems. Annals of Eugenics 7, 179-188, 1936. 21. Chiu, S. and Cheng, J. Automatic generation of fuzzy rulebase for robot arm posture selection. Proc. 1st Joint Conf. of North American Fuzzy Information Processing Society (NAFIPS ‘94), Industrial Fuzzy Control & Intelligent Systems Conf., and NASA Joint Technology Workshop on Neural Networks & Fuzzy Logic, San Antonio, TX, December 18-21, 436-440, 1994.