Luận văn thạc sĩ khoa học máy tính: Dự báo chuỗi thời gian với mô hình ARIMA và giải thuật di truyền

Luận văn thạc sĩ phân tích máy tính dự báo chuỗi thời gian sử dụng mô hình arima và giải thuật di truyền, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho thực

• Tác giả: Lâm Hoàng Vũ
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - Đại học Quốc Gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Dự Báo Chuỗi Thời Gian Bằng Mô Hình ARIMA Và Giải Thuật Di Truyền
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu về Dự báo chuỗi thời gian

Dự báo chuỗi thời gian là một lĩnh vực quan trọng trong khoa học máy tính, đặc biệt trong việc phân tích dữ liệu. Dự báo chuỗi thời gian sử dụng các mô hình như mô hình ARIMA để dự đoán các giá trị tương lai dựa trên dữ liệu quá khứ. Mô hình ARIMA, viết tắt của Autoregressive Integrated Moving Average, là một trong những công cụ mạnh mẽ nhất trong phân tích chuỗi thời gian. Việc lựa chọn mô hình ARIMA phù hợp thường dựa vào phương pháp Box-Jenkins, tuy nhiên, phương pháp này phụ thuộc nhiều vào kinh nghiệm của người phân tích. Do đó, việc áp dụng giải thuật di truyền để tự động hóa quá trình này là một bước tiến quan trọng. Giải thuật di truyền giúp tối ưu hóa việc lựa chọn mô hình và ước lượng các tham số của mô hình một cách hiệu quả hơn.

1.1. Tầm quan trọng của Dự báo chuỗi thời gian

Dự báo chuỗi thời gian có ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, tài chính, và khoa học tự nhiên. Việc phân tích và dự đoán các xu hướng trong dữ liệu chuỗi thời gian giúp các nhà nghiên cứu và doanh nghiệp đưa ra quyết định chính xác hơn. Các ứng dụng cụ thể bao gồm dự đoán giá cổ phiếu, phân tích xu hướng tiêu dùng, và dự báo thời tiết. Sự phát triển của công nghệ thông tin và khoa học dữ liệu đã tạo điều kiện thuận lợi cho việc áp dụng các mô hình phức tạp như ARIMA trong thực tiễn. Điều này không chỉ giúp cải thiện độ chính xác của dự báo mà còn tiết kiệm thời gian và nguồn lực cho các tổ chức.

II. Mô hình ARIMA và Giải thuật di truyền

Mô hình ARIMA là một trong những mô hình phổ biến nhất trong phân tích dữ liệu chuỗi thời gian. Mô hình này kết hợp giữa tự hồi quy và trung bình di động, cho phép phân tích các chuỗi dữ liệu có tính chất ngẫu nhiên. Tuy nhiên, việc xác định bậc của mô hình ARIMA là một thách thức lớn. Giải thuật di truyền, một phương pháp tối ưu hóa dựa trên nguyên lý chọn lọc tự nhiên, đã được áp dụng để giải quyết vấn đề này. Giải thuật di truyền có khả năng tìm kiếm không gian giải pháp rộng lớn và hiệu quả hơn so với các phương pháp truyền thống. Việc sử dụng giải thuật di truyền trong mô hình ARIMA không chỉ giúp xác định bậc của mô hình mà còn ước lượng các tham số một cách tự động, từ đó nâng cao độ chính xác của dự báo.

2.1. Cấu trúc của mô hình ARIMA

Mô hình ARIMA bao gồm ba thành phần chính: AR (tự hồi quy), I (tích phân), và MA (trung bình di động). Thành phần AR mô tả mối quan hệ giữa giá trị hiện tại và các giá trị trước đó, trong khi thành phần MA mô tả mối quan hệ giữa giá trị hiện tại và các sai số trong quá khứ. Tích phân được sử dụng để làm cho chuỗi dữ liệu trở nên ổn định. Việc lựa chọn bậc cho các thành phần này là rất quan trọng và ảnh hưởng trực tiếp đến độ chính xác của mô hình. Giải thuật di truyền giúp tự động hóa quá trình này, từ đó giảm thiểu sai sót do yếu tố con người.

III. Kết quả thực nghiệm và ứng dụng

Kết quả thực nghiệm cho thấy mô hình GA-ARMA sử dụng giải thuật di truyền đã đạt được hiệu quả cao hơn so với các phương pháp truyền thống. Việc áp dụng giải thuật di truyền không chỉ giúp tối ưu hóa bậc của mô hình mà còn cải thiện độ chính xác trong việc ước lượng các tham số. Các thử nghiệm trên nhiều tập dữ liệu khác nhau cho thấy mô hình này có khả năng dự đoán tốt hơn, đồng thời thời gian chạy cũng được cải thiện đáng kể. Điều này chứng tỏ rằng việc kết hợp giữa mô hình ARIMA và giải thuật di truyền là một hướng đi tiềm năng trong nghiên cứu và ứng dụng thực tiễn.

3.1. Ứng dụng trong thực tiễn

Mô hình GA-ARMA có thể được áp dụng trong nhiều lĩnh vực khác nhau như tài chính, y tế, và sản xuất. Trong tài chính, mô hình này có thể giúp dự đoán giá cổ phiếu, từ đó hỗ trợ các nhà đầu tư đưa ra quyết định. Trong y tế, việc dự đoán các chỉ số sức khỏe từ dữ liệu chuỗi thời gian có thể giúp cải thiện chất lượng chăm sóc bệnh nhân. Ngoài ra, trong sản xuất, mô hình này có thể được sử dụng để dự đoán nhu cầu sản phẩm, từ đó tối ưu hóa quy trình sản xuất. Sự kết hợp giữa khoa học máy tính và phân tích dữ liệu sẽ mở ra nhiều cơ hội mới cho các ứng dụng trong tương lai.

Trích đoạn nội dung tài liệu

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC BÁCH KHOA LÂM HOÀNG VŨ DỰ BÁO CHUỖI THỜI GIAN SỬ DỤNG MÔ HÌNH ARIMA VÀ GIẢI THUẬT DI TRUYỀN Chuyên Ngành: Khoa Học Máy Tính Mã số: 60.01 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 07 năm 2012 ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độc Lập - Tự Do - Hạnh Phúc ---------------- ---oOo--- Tp.

NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: Lâm Hoàng Vũ.Giới tính: Nam �/ Nữ � Ngày, tháng, năm sinh: 14/10/1981….Nơi sinh: Quảng Ngãi Chuyên ngành: Khoa học Máy tính…………………………………………………………………. Khoá: 2008……………………………………………………………………………………………… 1- TÊN ĐỀ TÀI: DỰ BÁO CHUỖI THỜI GIAN SỬ DỤNG MÔ HÌNH ARIMA VÀ GIẢI THUẬT DI TRUYỀN. 2- NHIỆM VỤ LUẬN VĂN:. 3- NGÀY GIAO NHIỆM VỤ:.

4- NGÀY HOÀN THÀNH NHIỆM VỤ:. 5- HỌ VÀ TÊN CÁN BỘ HƢỚNG DẪN: PGS TS. Dƣơng Tuấn Anh……………. Nội dung và đề cƣơng Luận văn thạc sĩ đã đƣợc Hội Đồng Chuyên Ngành thông qua.

CÁN BỘ HƢỚNG DẪN CHỦ NHIỆM BỘ MÔN (Họ tên và chữ ký) QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) PGS TS. Dƣơng Tuấn Anh TS. Đinh Đức Anh Vũ CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hƣớng dẫn khoa học: PGS TS. Dƣơng Tuấn Anh.

Cán bộ chấm nhận xét 1:. Cán bộ chấm nhận xét 2:. Luận văn thạc sĩ đƣợc bảo vệ tại. HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƢỜNG ĐẠI HỌC BÁCH KHOA, Ngày.

2012 LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác nhƣ đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chƣa có phần nội dung nào của luận văn này đƣợc nộp để lấy một bằng cấp ở trƣờng này hoặc trƣờng khác. Ngày 01 tháng 07 năm 2012 Lâm Hoàng Vũ i LỜI CÁM ƠN Tôi xin bày tỏ lòng biết ơn chân thành nhất đến PGS. Dƣơng Tuấn Anh, Thầy đã tận tâm chỉ dẫn, truyền đạt những kiến thức và kinh nghiệm quý báu cho tôi từ những ngày đầu cũng nhƣ những ngày cuối trong suốt quá trình thực hiện luận văn này. Tôi cũng xin đƣợc gửi lời cám ơn đến các quí Thầy Cô giáo tham gia giảng dạy chƣơng trình cao học ở khoa Khoa Học và Kỹ Thuật Máy Tính, trƣờng Đại Học Bách Khoa TP.

Hồ Chí Minh đã trang bị cho tôi những kiến thức nền tảng quan trọng trong suốt quá trình tôi theo học. Và cuối cùng, tôi xin đƣợc gửi lời cám ơn đến gia đình và bạn bè, những ngƣời đã động viên tôi trong suốt thời gian vừa qua. ii TÓM TẮT LUẬN VĂN Các nghiên cứu về dữ liệu chuỗi thời gian đem lại những ứng dụng thực tế quan trọng trong các lĩnh vực nhƣ thống kê, xử lý tín hiệu số, toán tài chính, … Một trong số đó là bài dự báo chuỗi thời gian (hay dự báo các giá trị tƣơng lai của chuỗi thời gian từ các giá trị trong quá khứ) từ việc xây dựng các mô hình dự báo thích hợp. Đã có nhiều nghiên cứu tập trung vào bài toán dự báo chuỗi thời gian, một trong số đó là sử dụng mô hình ARIMA, mô hình ARMA, trong đó việc lựa chọn mô hình dựa theo phƣơng pháp của Box-Jenkins và việc ƣớc lƣợng các hệ số của mô hình dựa trên các phƣơng pháp toán học thuần túy rất phức tạp.

Hơn nữa, kết quả của phƣơng pháp Box-Jenkins phụ thuộc rất nhiều vào năng lực chuyên môn của ngƣời làm dự báo. Để giải quyết vấn đề này, có nhiều phƣơng pháp meta-heuristic sử dụng giải thuật di truyền đƣợc đề xuất để việc lựa chọn mô hình (thể hiện qua bậc và các biến thời gian trễ có mặt trong mô hình) và tính toán các hệ số của mô hình một cách tự động. Tuy vậy, việc sinh ra các mô hình trong quá trình tìm kiếm lời giải của các phƣơng pháp meta-heuristic đƣợc thực hiện mang tính chất ngẫu nhiên (bởi bản chất của các giải thuật di truyền, giải thuật mô phỏng luyện kim) và các phƣơng pháp meta-heuristic này thƣờng chạy rất chậm để cho ra lời giải tốt. Từ những vấn đề nêu trên, trong đề tài này, cũng với mục tiêu đƣa ra một phƣơng pháp để tự động xác định bậc và ƣớc lƣợng các hệ số của mô hình ARMA, chúng tôi đề xuất một phƣơng pháp mở rộng không gian tìm kiếm các lời giải của mô hình ARMA dựa trên giải thuật tìm kiếm Tabu trong việc xác định bậc và sử dụng giải thuật di truyền để ƣớc lƣợng các hệ số của mô hình ARMA.

Kết quả thực nghiệm cho thấy phƣơng pháp mới này đem lại kết quả tốt hơn đối với hầu hết các chuỗi dữ liệu đƣợc kiểm tra so với các phƣơng pháp meta-heuristic khác và thời gian chạy dừng ở mức có thể chấp nhận đƣợc. iii MỤC LỤC LỜI CAM ĐOAN .ii TÓM TẮT LUẬN VĂN. iii MỤC LỤC .iv DANH MỤC HÌNH .vii DANH MỤC BẢNG .ix DANH MỤC TỪ VIẾT TẮT .1 Dữ liệu chuỗi thời gian .2 Các thành phần của chuỗi thời gian .3 Ứng dụng của phân tích dữ liệu chuỗi thời gian .4 Một số vấn đề thƣờng gặp khi nghiên cứu chuỗi thời gian .2 Bài toán dự báo chuỗi thời gian .3 Động cơ và mục tiêu nghiên cứu .4 Tóm lƣợc các kết quả đạt đƣợc .5 Cấu trúc của luận văn. TỔNG QUAN VỀ PHƢƠNG PHÁP VÀ MÔ HÌNH DỰ BÁO CHUỖI THỜI GIAN .1 Các mô hình làm trơn và ngoại suy dữ liệu chuỗi thời gian .2 Mô hình làm trơn hàm mũ .3 Dự báo bằng phân tích xu hƣớng .2 Các mô hình dự báo tuyến tính .3 Các mô hình dự báo phi tuyến .1 Mạng nơ-ron nhân tạo (ANN) .2 Các mô hình phi tuyến khác .1 Các kiến thức cơ bản về chuỗi thời gian.1 Quá trình ngẫu nhiên .2 Quá trình ngẫu nhiên tĩnh .3 Quá trình không tĩnh thuần nhất .2 Quá trình ARMA .1 Quá trình trung bình di động .2 Quá trình tự hồi qui .3 Quá trình ARMA .3 Giải thuật di truyền .1 Cách biểu diễn di truyền cho lời giải của bài toán .2 Cách khởi tạo quần thể ban đầu .3 Phép toán chọn lọc .4 Phép toán lai .5 Phép toán đột biến .6 Các tham số của giải thuật .7 Điều kiện dừng của giải thuật.4 Mô hình ARMA sử dụng giải thuật di truyền.1 Ánh xạ mô hình ARMA thành nhiễm sắc thể .2 Phƣơng pháp siêu tiến hóa cho mô hình ARMA.

PHƢƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ.1 Giải thuật tìm kiếm Tabu .2 Mô hình GA-ARMA.1 Phép toán lai .2 Phép toán đột biến .3 Khởi tạo lời giải ban đầu đối với giải thuật tìm kiếm Tabu .4 Phƣơng pháp tìm tập con lân cận .5 Hiệu chỉnh giải thuật tìm kiếm Tabu. KẾT QUẢ THỰC NGHIỆM .1 Dữ liệu thực nghiệm .2 Kết quả thực nghiệm và đánh giá .2 Hƣớng phát triển đề tài. 70 TÀI LIỆU THAM KHẢO. 71 LÝ LỊCH TRÍCH NGANG.

75 QUÁ TRÌNH ĐÀO TẠO. 76 QUÁ TRÌNH CÔNG TÁC. 77 vi DANH MỤC HÌNH Hình 1.1: Đƣờng biểu diễn dữ liệu chuỗi thời gian cho chỉ số VN-Index từ ngày 3/1/2006 đến ngày 6/8/2008 .2: Minh họa về dữ liệu chuỗi thời gian theo dõi quá trình đo nhiệt độ .3: Đồ thị chuỗi thời gian và các giá trị dự báo .1: Đƣờng cong xu hƣớng dùng phƣơng pháp trung bình di động.2: Kiến trúc của một ANN cho dự báo chuỗi thời gian với 3 ngõ vào, một lớp ẩn hai nơ-ron và một ngõ ra (là giá trị dự báo) .1: Chi tiết hoạt động của một giải thuật di truyền chuẩn .2: Minh họa bánh xe Roulette .5: Minh họa cho việc giải mã của một nhiễm sắc thể trong meta-level .6: Phƣơng pháp siêu tiến hóa .1: Kiến trúc hai mức của M.Sơn và các cộng sự [28] .2: Quá trình lựa chọn lời giải tốt nhất ở mỗi bƣớc lặp.3: Giải thuật tìm kiếm Tabu sử dụng tiêu chuẩn kỳ vọng .4: Nhiễm sắc thể biểu diễn thực đại diện trong mô hình GA-ARMA .5: Minh họa cho phép toán lai số học .6: Thủ tục xác định tập con các lời giải lân cận .7: Minh họa so sánh các tham số của lời giải với giá trị ngƣỡng để tạo ra các bƣớc chuyển .8: Kết nối các lời giải trong cùng tập con lân cận .9: Giải thuật tìm kiếm Tabu đƣợc hiệu chỉnh .1: Đồ thị chuỗi dữ liệu Passengers .2: Đồ thị chuỗi dữ liệu Paper .3: Đồ thị chuỗi dữ liệu Deaths .4: Đồ thị chuỗi dữ liệu Maxtemp .5: Đồ thị chuỗ dữ liệu Chemical .6: Đồ thị chuỗi dữ liệu Prices .7: Đồ thị chuỗi dữ liệu Sunspots .8: Đồ thị chuỗi dữ liệu Kobe .9: Đồ thị dự báo tập dữ liệu Passengers .10: Đồ thị dự báo tập dữ liệu Paper .11: Đồ thị dự báo tập dữ liệu Deaths .12: Đồ thị dự báo tập dữ liệu Maxtemp .13: Đồ thị dự báo tập dữ liệu Chemical .14: Đồ thị dự báo tập dữ liệu Prices .15: Đồ thị dự báo tập dữ liệu Sunspot .16: Đồ thị dự báo tập dữ liệu Kobe. 67 viii DANH MỤC BẢNG Bảng 5.1: Phân loại các tập dữ liệu đƣợc sử dụng để thực nghiệm .2: Những mô hình ARMA tốt nhất tìm đƣợc bởi phƣơng pháp đề nghị .3: So sánh kết quả của các phƣơng pháp dự báo khác nhau .4: Thời gian chạy giải thuật Tabu-SA của các chuỗi dữ liệu thực nghiệm.

68 ix DANH MỤC TỪ VIẾT TẮT ACF Hàm tự tƣơng quan (Autocorrelation Function) ACVF Hàm tự hiệp phƣơng sai (Autocovariance Function) ANN Mạng nơ-ron nhân tạo (Artificial Neural Network) AR Tự hồi qui (Autoregression) ARIMA Tự hồi qui kết hợp trung bình di động (Autoregression Integrated Moving Average) ARMA Tự hồi qui – Trung bình di động (Autoregression Moving Average) EWMA Trung bình di động có trọng số theo mũ (Exponentially Weighted Moving Average) GA Giải thuật di truyền (Genetic Algorithm) HMM Mô hình Markov ẩn (Hidden Markov Model) MA Trung bình di động (Moving Average) NST Nhiễm sắc thể (Chromosome) PACF Hàm tự tƣơng quan riêng phần (Partial Autocorrelation Function) x Luận văn thạc sĩ GVHD: PGS. Dƣơng Tuấn Anh Chƣơng 1.1 Dữ liệu chuỗi thời gian 1.1 Định nghĩa Chuỗi thời gian là một tập hợp dữ liệu các quan sát đo đƣợc một cách tuần tự theo thời gian. Các quan sát này có thể đo đƣợc một cách liên tục theo thời gian hoặc là có thể đƣợc lấy theo một tập rời rạc các thời điểm khác nhau.