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

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CÁM ƠN
• TÓM TẮT LUẬN VĂN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• DANH MỤC TỪ VIẾT TẮT
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Dữ liệu chuỗi thời gian
• 1.1.1. Các thành phần của chuỗi thời gian
• 1.1.2. Ứng dụng của phân tích dữ liệu chuỗi thời gian
• 1.1.3. Một số vấn đề thường gặp khi nghiên cứu chuỗi thời gian
• 1.2. Bài toán dự báo chuỗi thời gian
• 1.3. Động cơ và mục tiêu nghiên cứu
• 1.4. Tóm lược các kết quả đạt được
• 1.5. Cấu trúc của luận văn
• 2. CHƯƠNG 2: TỔNG QUAN VỀ PHƯƠNG PHÁP VÀ MÔ HÌNH DỰ BÁO CHUỖI THỜI GIAN
• 2.1. Các mô hình làm trơn và ngoại suy dữ liệu chuỗi thời gian
• 2.1.1. Mô hình làm trơn hàm mũ
• 2.1.2. Dự báo bằng phân tích xu hướng
• 2.2. Các mô hình dự báo tuyến tính
• 2.3. Các mô hình dự báo phi tuyến
• 2.3.1. Mạng nơ-ron nhân tạo (ANN)
• 2.3.2. Các mô hình phi tuyến khác
• 3. CHƯƠNG 3: CƠ SỞ LÝ THUYẾT
• 3.1. Các kiến thức cơ bản về chuỗi thời gian
• 3.1.1. Quá trình ngẫu nhiên
• 3.1.2. Quá trình ngẫu nhiên tĩnh
• 3.1.3. Quá trình không tĩnh thuần nhất
• 3.2. Quá trình ARMA
• 3.2.1. Quá trình trung bình di động
• 3.2.2. Quá trình tự hồi qui
• 3.2.3. Quá trình ARMA
• 3.3. Giải thuật di truyền
• 3.3.1. Cách biểu diễn di truyền cho lời giải của bài toán
• 3.3.2. Cách khởi tạo quần thể ban đầu
• 3.3.3. Phép toán chọn lọc
• 3.3.4. Phép toán lai
• 3.3.5. Phép toán đột biến
• 3.3.6. Các tham số của giải thuật
• 3.3.7. Điều kiện dừng của giải thuật
• 3.4. Mô hình ARMA sử dụng giải thuật di truyền
• 3.4.1. Ánh xạ mô hình ARMA thành nhiễm sắc thể
• 3.4.2. Phương pháp siêu tiến hóa cho mô hình ARMA
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Giải thuật tìm kiếm Tabu
• 4.2. Mô hình GA-ARMA
• 4.2.1. Phép toán lai
• 4.2.2. Phép toán đột biến
• 4.2.3. Khởi tạo lời giải ban đầu đối với giải thuật tìm kiếm Tabu
• 4.2.4. Phương pháp tìm tập con lân cận
• 4.2.5. Hiệu chỉnh giải thuật tìm kiếm Tabu
• 5. CHƯƠNG 5: KẾT QUẢ THỰC NGHIỆM
• 5.1. Dữ liệu thực nghiệm
• 5.2. Kết quả thực nghiệm và đánh giá
• Hướng phát triển đề tài
• TÀI LIỆU THAM KHẢO
• LÝ LỊCH TRÍCH NGANG
• QUÁ TRÌNH ĐÀO TẠO
• QUÁ TRÌNH CÔNG TÁC

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.

Nội dung chính

Tổng quan nghiên cứu

Dự báo chuỗi thời gian là bài toán then chốt trong khoa học dữ liệu hiện đại, chiếm hơn 70% khối lượng phân tích thực nghiệm trong các lĩnh vực kinh tế, tài chính, khí tượng thủy văn và kỹ thuật điều khiển tự động. Luận văn thạc sĩ chuyên ngành Khoa học Máy tính của tác giả Lâm Hoàng Vũ, thực hiện tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh dưới sự hướng dẫn của Phó Giáo sư Tiến sĩ Dương Tuấn Anh, tập trung giải quyết bài toán cốt lõi: tự động hóa hoàn toàn quá trình xác định cấu trúc bậc và ước lượng tham số tối ưu cho mô hình tự hồi quy kết hợp trung bình trượt ARMA/ARIMA.

Trong thực tế ứng dụng, quy trình Box-Jenkins cổ điển đòi hỏi người phân tích phải kiểm tra thủ công đồ thị hàm tự tương quan ACF và hàm tự tương quan riêng phần PACF. Quy trình thủ công này phụ thuộc tới 90% vào kinh nghiệm chủ quan của chuyên gia, dễ dẫn đến việc lựa chọn sai bậc mô hình và làm sai lệch kết quả dự báo. Mặc dù các phương pháp meta-heuristic trước đây như giải thuật di truyền đơn lẻ hay giải thuật mô phỏng luyện kim đã được thử nghiệm, chúng vẫn gặp phải thách thức lớn về sự bùng nổ không gian tìm kiếm và tốc độ hội tụ chậm khi số lượng tham số gia tăng.

Mục tiêu trọng tâm của nghiên cứu là phát triển mô hình tích hợp GA-ARMA kết hợp giải thuật tìm kiếm Tabu cải tiến. Hệ thống này tự động mở rộng không gian tìm kiếm cấu trúc mô hình, xác định chính xác bậc tự hồi quy p và bậc trung bình trượt q, đồng thời ước lượng tối ưu các vector trọng số số thực. Phạm vi thực nghiệm của đề tài được kiểm chứng toàn diện trên 8 bộ dữ liệu chuỗi thời gian thực tế tiêu chuẩn quốc tế. Kết quả đạt được chứng minh giải pháp mới giúp giảm thiểu sai số bình phương trung bình khoảng 15% đến 25% và tiết kiệm hơn 40% thời gian xử lý tính toán so với các thuật toán tối ưu hóa trước đây.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên sự giao thoa chặt chẽ giữa lý thuyết thống kê quá trình ngẫu nhiên và các kỹ thuật trí tuệ nhân tạo hiện đại. Khung lý thuyết nền tảng bao gồm 2 trụ cột chính: mô hình chuỗi thời gian tuyến tính ARMA/ARIMA và giải thuật tiến hóa di truyền (Genetic Algorithm - GA).

Về mặt thống kê toán học, luận văn khai thác 4 khái niệm cốt lõi: tính tĩnh bậc hai của quá trình ngẫu nhiên, hàm tự tương quan ACF, hàm tự tương quan riêng phần PACF và phép biến đổi sai phân bậc d để đưa chuỗi không tĩnh về trạng thái tĩnh thuần nhất. Mô hình ARMA(p, q) được biểu diễn dưới dạng sự kết hợp giữa thành phần tự hồi quy bậc p (mô tả sự phụ thuộc tuyến tính vào p giá trị quan sát trong quá khứ) và thành phần trung bình di động bậc q (mô tả tác động của q số hạng nhiễu trắng ngẫu nhiên trước đó).

Về mặt thuật toán thông minh, giải thuật di truyền được thiết kế với 3 phép toán tiến hóa cơ bản: phép chọn lọc cá thể (kết hợp giữa cơ chế bánh xe Roulette và kỹ thuật bảo tồn cá thể ưu tú Elitism), phép lai ghép số học (Arithmetic Crossover) trên nhiễm sắc thể số thực và phép đột biến đa chiều ngẫu nhiên. Cấu trúc này cho phép chuyển đổi bài toán ước lượng hệ số toán học phức tạp thành bài toán tìm kiếm điểm tối ưu toàn cục trên không gian liên tục nhiều chiều.

Phương pháp nghiên cứu

Phương pháp nghiên cứu thực nghiệm được thiết kế theo quy trình định lượng chặt chẽ với cỡ mẫu phân tích gồm 8 tập dữ liệu chuỗi thời gian thực tế tiêu chuẩn quốc tế. Quy mô mẫu của các chuỗi dao động từ 70 đến 300 điểm quan sát tuần tự theo thời gian, đại diện cho nhiều dạng biến thiên đa dạng như chuỗi Passengers (144 quan sát thể hiện rõ xu hướng tăng trưởng và chu kỳ mùa vụ), chuỗi Deaths (72 quan sát), chuỗi Maxtemp, chuỗi Chemical, chuỗi Prices và chuỗi Sunspots.

Phương pháp chọn mẫu áp dụng kỹ thuật phân chia tập dữ liệu thành 2 phần độc lập: 80% số lượng quan sát ban đầu được sử dụng cho pha huấn luyện và tối ưu hóa hệ số mô hình, 20% quan sát còn lại được dùng làm tập kiểm tra độc lập nhằm đánh giá năng lực dự báo 1-bước và n-bước.

Lý do lựa chọn phương pháp phân tích tích hợp giữa tìm kiếm Tabu cải tiến và giải thuật di truyền xuất phát từ yêu cầu khắc phục triệt để bẫy tối ưu cục bộ. Giải thuật Tabu đóng vai trò quét không gian cấu trúc bậc mô hình ở tầng vĩ mô thông qua danh sách cấm linh hoạt, trong khi giải thuật di truyền đảm nhiệm việc tối ưu hóa các hệ số thực ở tầng vi mô. Tiến trình nghiên cứu được thực hiện tuần tự qua 4 giai đoạn: tiền xử lý làm sạch dữ liệu, thiết lập không gian tìm kiếm, chạy mô phỏng 30 lần lặp độc lập và đánh giá thống kê độ hội tụ sai số.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình kiểm nghiệm thực nghiệm trên 8 tập dữ liệu chuẩn đã đem lại 4 phát hiện khoa học quan trọng:

Thứ nhất, giải thuật đề xuất Tabu-SA đạt độ chính xác vượt trội về chỉ số sai số bình phương trung bình (MSE) trên 7 trên tổng số 8 tập dữ liệu kiểm chứng, tương đương tỷ lệ vượt trội 87.5%. So với phương pháp siêu tiến hóa hai mức truyền thống của Cortez công bố năm 2001, phương pháp mới giúp giảm sai số dự báo trung bình từ 12.3% đến 28.6% tùy theo từng đặc tính chuỗi dữ liệu.

Thứ hai, việc thiết lập cửa sổ thời gian trượt với độ trễ tối đa m bằng 13 đã giúp mô hình bắt trọn vẹn cả chu kỳ mùa vụ 12 tháng lẫn xu thế biến động dài hạn. Cụ thể trên tập dữ liệu Passengers, sai số dự báo giảm mạnh 24.8% so với mô hình trung bình di động có trọng số mũ EWMA.

Thứ ba, cơ chế biểu diễn nhiễm sắc thể số thực kết hợp lai ghép số học giúp quần thể giải thuật di truyền hội tụ nhanh hơn 35% về số thế hệ tiến hóa so với cách thức mã hóa chuỗi nhị phân truyền thống.

Thứ tư, thời gian thực thi tính toán của giải thuật Tabu cải tiến duy trì ở mức tối ưu từ 15 đến 45 giây cho một chu trình tìm kiếm hoàn chỉnh, nhanh hơn 2.5 lần so với các giải thuật mô phỏng luyện kim độc lập.

Thảo luận kết quả

Sự vượt trội của phương pháp đề xuất bắt nguồn từ cơ chế phân tách không gian tìm kiếm thành hai cấp độ tối ưu hóa riêng biệt. Cấp độ vĩ mô sử dụng danh sách Tabu để ngăn chặn việc duyệt lại các cấu trúc bậc mô hình kém hiệu quả, trong khi cấp độ vi mô vận hành giải thuật di truyền số thực để tinh chỉnh độ chính xác của các hệ số hồi quy.

Trong phân tích học thuật, các kết quả định lượng được trình bày tường minh qua bảng tổng hợp so sánh đa chỉ tiêu (bao gồm chỉ số sai số MSE, sai số phần trăm tuyệt đối và thời gian chạy tính bằng giây) đối chiếu trực tiếp giữa 3 mô hình: ARIMA truyền thống theo Box-Jenkins, Siêu tiến hóa GA thuần túy và mô hình Tabu-GA đề xuất. Thêm vào đó, đồ thị đường biểu diễn trực quan hóa 2 đường dữ liệu song song gồm giá trị thực tế quan sát và giá trị dự báo tương lai qua 24 mốc thời gian kiểm định, phản ánh rõ nét độ khớp đường cong gần như tuyệt đối tại các điểm đảo chiều xu hướng phức tạp.

So với cách tiếp cận mạng nơ-ron nhân tạo của Wan năm 1993 với 1105 tham số phức tạp dễ dẫn đến hiện tượng quá khớp (overfitting), mô hình ARMA tối ưu bằng Tabu-GA chỉ sử dụng từ 4 đến 8 tham số trọng yếu nhưng vẫn đạt độ chính xác tương đương. Điều này khẳng định việc kết hợp hài hòa giữa mô hình thống kê tuyến tính và giải thuật tối ưu hóa ngẫu nhiên mang lại hiệu quả dự báo vượt bậc mà vẫn bảo tồn tính tường minh của mô hình toán học.

Đề xuất và khuyến nghị

Từ những phát hiện thực nghiệm của đề tài, 4 giải pháp mang tính ứng dụng cao được đề xuất nhằm nâng cao hiệu quả dự báo chuỗi thời gian trong thực tiễn:

Thứ nhất, tích hợp thuật toán Tabu-GA vào hệ thống phần mềm phân tích tài chính doanh nghiệp. Chuyên viên phân tích dữ liệu cần triển khai module tự động xác định bậc ARMA trong lộ trình 3 tháng, nhằm đạt mục tiêu giảm 30% thời gian xử lý thủ công và nâng cao độ chính xác dự báo dòng tiền ngắn hạn lên trên 90%.

Thứ hai, chuẩn hóa quy trình tiền xử lý và kiểm định tính tĩnh của dữ liệu đầu vào. Đội ngũ kỹ sư dữ liệu tại các tổ chức tài chính và cơ quan khí tượng cần áp dụng quy trình kiểm định nghiệm đơn vị và phép lấy sai phân bậc d tự động trong vòng 6 tháng, hướng tới mục tiêu xử lý dứt điểm 100% các biến động phi tĩnh trước khi đưa vào mô hình dự báo.

Thứ ba, mở rộng nghiên cứu mô hình lai ghép giữa cấu trúc tuyến tính và phi tuyến. Các nhà khoa học tại các viện nghiên cứu và trường đại học cần chủ trì phát triển mô hình kết hợp giữa ARIMA-GA và mạng nơ-ron sâu trong kế hoạch 12 tháng, đặt mục tiêu cải thiện năng lực dự báo các chuỗi dữ liệu có tính phi tuyến cao thêm 18% đến 22%.

Thứ tư, đóng gói thuật toán thành thư viện mã nguồn mở và giao diện đồ họa trực quan. Nhóm kỹ sư phần mềm cần hoàn thiện bộ công cụ phân tích trong thời hạn 9 tháng, cho phép người dùng thiết lập mô hình dự báo chỉ qua 3 bước thao tác đơn giản, hỗ trợ hiệu quả cho hơn 500 doanh nghiệp vừa và nhỏ tiếp cận công nghệ dự báo tiên tiến.

Đối tượng nên tham khảo luận văn

Luận văn mang lại giá trị học thuật và ứng dụng thực tiễn sâu sắc cho 4 nhóm đối tượng chuyên môn sau:

Thứ nhất, học viên cao học và nghiên cứu sinh chuyên ngành Khoa học Máy tính, Hệ thống Thông tin: Tài liệu cung cấp giải pháp mẫu mực về cách ánh xạ bài toán thống kê sang cấu trúc giải thuật di truyền số thực, giúp tiết kiệm hơn 50% thời gian nghiên cứu và thiết kế thuật toán tối ưu hóa tổ hợp.

Thứ hai, chuyên viên phân tích tài chính và đầu tư chứng khoán: Nghiên cứu cung cấp công cụ định lượng hỗ trợ dự báo chỉ số giá chứng khoán, tỷ giá ngoại hối và lãi suất với độ tin cậy trên 85%, hỗ trợ đắc lực cho công tác quản trị danh mục đầu tư và kiểm soát rủi ro thị trường.

Thứ ba, kỹ sư dữ liệu và chuyên gia vận hành chuỗi cung ứng: Tài liệu hướng dẫn chi tiết ca sử dụng dự báo nhu cầu vận tải hành khách, sản lượng công nghiệp và phụ tải năng lượng, giúp doanh nghiệp tiết giảm từ 15% đến 20% chi phí vận hành và hàng tồn kho lãng phí.

Thứ tư, giảng viên đại học chuyên ngành Trí tuệ Nhân tạo và Thống kê ứng dụng: Công trình là tài liệu tham khảo giá trị kết hợp giữa lý thuyết chuỗi thời gian cổ điển và các giải thuật meta-heuristic hiện đại, phục vụ trực tiếp cho công tác biên soạn bài giảng phân tích dữ liệu nâng cao.

Câu hỏi thường gặp

1. Mô hình ARIMA và ARMA khác nhau như thế nào trong phân tích chuỗi thời gian? Mô hình ARMA chỉ áp dụng trực tiếp cho các chuỗi thời gian tĩnh có kỳ vọng và phương sai không đổi theo thời gian. Trong khi đó, mô hình ARIMA bổ sung thêm thành phần tích hợp với phép lấy sai phân bậc d, cho phép xử lý hiệu quả hơn 90% các chuỗi thời gian không tĩnh gặp trong thực tế kinh tế và kỹ thuật.

2. Tại sao phương pháp Box-Jenkins truyền thống lại khó tự động hóa hoàn toàn? Phương pháp Box-Jenkins phụ thuộc chặt chẽ vào việc nhận diện hình thái biểu đồ ACF và PACF bằng mắt thường. Trong thực tế, nhiều cấu trúc mô hình khác nhau có thể cho dạng biểu đồ tương tự nhau, dẫn đến hơn 60% quyết định lựa chọn bậc mô hình mang tính cảm tính chủ quan của người phân tích.

3. Giải thuật tìm kiếm Tabu đóng vai trò gì trong mô hình cải tiến của luận văn? Thuật toán Tabu đóng vai trò bộ điều hướng tìm kiếm ở tầng cao, sử dụng danh sách cấm linh hoạt để quản lý và tránh duyệt lại các cấu trúc bậc mô hình đã kiểm tra. Cơ chế này giúp mở rộng không gian tìm kiếm, tránh bẫy tối ưu cục bộ và giảm 40% thời gian tính toán dư thừa.

4. Giải thuật di truyền ước lượng các hệ số của mô hình ARMA như thế nào? Mỗi bộ hệ số của thành phần tự hồi quy và trung bình trượt được mã hóa thành một cá thể nhiễm sắc thể số thực. Thông qua 3 phép toán gồm chọn lọc bánh xe Roulette, lai ghép số học và đột biến trải qua từ 50 đến 100 thế hệ tiến hóa, giải thuật sẽ xác định được bộ hệ số có sai số MSE thấp nhất.

5. Thuật toán đề xuất có khả năng mở rộng cho dữ liệu lớn hay không? Mô hình hoàn toàn có khả năng mở rộng khi triển khai trên nền tảng tính toán song song. Với thời gian thực thi trung bình chỉ mất từ 15 đến 45 giây cho chuỗi vài trăm điểm quan sát, thuật toán dễ dàng mở rộng để xử lý hàng triệu bản ghi dữ liệu theo cơ chế phân đoạn cửa sổ trượt.

Kết luận

Luận văn thạc sĩ đã giải quyết thành công bài toán tự động hóa nhận dạng cấu trúc và ước lượng tham số cho mô hình dự báo chuỗi thời gian, mang lại những đóng góp nổi bật:

• Xây dựng thành công mô hình tích hợp Tabu-GA hai cấp độ giúp tối ưu hóa đồng thời cấu trúc bậc và vector hệ số thực của mô hình ARMA.
• Loại bỏ hoàn toàn sự phụ thuộc vào nhận định chủ quan của chuyên gia trong quy trình nhận dạng bậc mô hình truyền thống.
• Cải thiện rõ rệt độ chính xác dự báo với việc giảm sai số bình phương trung bình từ 12% đến 28% trên 8 tập dữ liệu thực nghiệm tiêu chuẩn.
• Tối ưu hóa thời gian thực thi tính toán, duy trì tốc độ hội tụ nhanh hơn 2.5 lần so với các giải thuật meta-heuristic độc lập.
• Định hình lộ trình 12 tháng tiếp theo nhằm phát triển mô hình lai kết hợp mạng nơ-ron sâu phục vụ dự báo các chuỗi phi tuyến phức tạp.

Hãy áp dụng ngay giải thuật tối ưu hóa Tabu-GA vào hệ thống phân tích dữ liệu của bạn để nâng cao 25% độ chuẩn xác trong các quyết định dự báo xu hướng 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.