Luận văn thạc sĩ HCMUTE: Dự báo chuỗi thời gian dựa trên so trùng mẫu

Luận văn thạc sĩ HCMUTE nghiên cứu dự báo chuỗi thời gian bằng phương pháp so trùng mẫu và các độ đo đa dạng, mang lại kết quả chính xác.

• Tác giả: Trần Trọng Bình
• Người hướng dẫn: TS. Nguyễn Thành Sơn
• Trường học: Trường Đại Học Sư Phạm Kỹ Thuật Thành Phố Hồ Chí Minh
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Dự Báo Trên Chuỗi Thời Gian Dựa Trên So Trùng Mẫu Sử Dụng Nhiều Độ Đo
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Đị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
• 1. CHƯƠNG I: TỔNG QUAN
• 2. CHƯƠNG II: CƠ SỞ LÝ THUYẾT
• 3. CHƯƠNG III: ĐỀ XUẤT PHƯƠNG PHÁP DỰ BÁO TRÊN CHUỖI THỜI GIAN DỰA TRÊN SO TRÙNG MẪU SỬ DỤNG NHIỀU ĐỘ ĐO
• 4. CHƯƠNG IV: THỰC NGHIỆM
• 5. CHƯƠNG V: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO
• DANH SÁCH CÁC CHỮ VIẾT TẮT
• DANH SÁCH CÁC BẢNG
• DANH MỤC HÌNH ẢNH

Tóm tắt

I. Tổng quan

Trong bối cảnh phát triển công nghệ thông tin, việc thu thập và lưu trữ dữ liệu ngày càng gia tăng. Tuy nhiên, chỉ một phần nhỏ trong số đó được phân tích, dẫn đến việc khai thác dữ liệu trở thành một nhu cầu cấp thiết. Dự báo chuỗi thời gian là một trong những ứng dụng quan trọng của khai thác dữ liệu, giúp cung cấp thông tin cần thiết cho việc ra quyết định. Các phương pháp dự báo hiện nay được chia thành hai loại chính: định tính và định lượng. Phương pháp định lượng, dựa trên dữ liệu lịch sử, cho phép phát hiện xu hướng và mô hình hóa các biến số trong tương lai. Các phương pháp như ARIMA, ANN, và SVM đã được phát triển để dự đoán chuỗi thời gian. Tuy nhiên, phân tích chuỗi thời gian dựa trên so trùng mẫu vẫn là một lĩnh vực đang được nghiên cứu và cải tiến.

II. Cơ sở lý thuyết

Khái niệm về chuỗi thời gian được định nghĩa là một chuỗi các giá trị số thực được đo tại các thời điểm cách đều nhau. Dữ liệu chuỗi thời gian thường bao gồm bốn thành phần: xu hướng dài hạn, thành phần mùa, thành phần chu kỳ và thành phần bất thường. Mỗi thành phần này có vai trò quan trọng trong việc phân tích và dự báo. Việc sử dụng nhiều độ đo khác nhau trong dự báo chuỗi thời gian có thể giúp khắc phục những nhược điểm của từng độ đo riêng lẻ. Các độ đo như Euclid, DTW, và LCSS đã được áp dụng trong nghiên cứu này để đánh giá hiệu quả của phương pháp dự báo. Sự kết hợp giữa các độ đo này có thể mang lại kết quả dự báo chính xác hơn.

III. Đề xuất phương pháp dự báo

Phương pháp dự báo được đề xuất trong luận văn này dựa trên so trùng mẫu sử dụng nhiều độ đo. Mô hình toán học được xây dựng dựa trên lý thuyết cực tiểu của đại số nhằm ước lượng các tham số ảnh hưởng đến các độ đo. Việc áp dụng các độ đo khác nhau trong dự báo cho phép mô hình có khả năng dự báo đa dạng các loại dữ liệu. Thực nghiệm đã được thực hiện trên ba độ đo: Euclid, DTW và LCSS để so sánh hiệu quả của phương pháp đề xuất. Kết quả cho thấy mô hình sử dụng nhiều độ đo cho kết quả dự báo tốt hơn so với mô hình chỉ sử dụng một độ đo.

IV. Thực nghiệm

Thực nghiệm được tiến hành trên nhiều bộ dữ liệu khác nhau để kiểm tra tính chính xác của mô hình dự báo. Các kết quả cho thấy rằng mô hình dự báo dựa trên so trùng mẫu sử dụng nhiều độ đo có độ chính xác cao hơn so với các phương pháp truyền thống. Việc áp dụng các độ đo khác nhau giúp cải thiện khả năng dự báo trong các tình huống khác nhau, từ đó khẳng định giá trị thực tiễn của nghiên cứu. Các số liệu thực nghiệm cho thấy rằng mô hình đề xuất có thể được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau, từ kinh tế đến khoa học kỹ thuật.

V. Kết luận và hướng phát triển

Luận văn đã đề xuất một phương pháp mới cho dự báo chuỗi thời gian dựa trên so trùng mẫu sử dụng nhiều độ đo. Kết quả thực nghiệm cho thấy mô hình này có khả năng dự báo tốt hơn so với các phương pháp hiện có. Hướng phát triển trong tương lai có thể bao gồm việc mở rộng mô hình để áp dụng cho các loại dữ liệu phức tạp hơn và cải thiện độ chính xác của dự báo. Nghiên cứu này không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn cao trong việc hỗ trợ ra quyết định trong các lĩnh vực khác nhau.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của công nghệ thông tin, lượng dữ liệu được thu thập và lưu trữ ngày càng tăng lên đáng kể, tuy nhiên chỉ khoảng 5% đến 10% trong số đó được phân tích và khai thác hiệu quả. Việc dự báo trên chuỗi thời gian trở thành một nhu cầu thiết yếu nhằm hỗ trợ các quyết định trong nhiều lĩnh vực như kinh tế, tài chính, kỹ thuật và khoa học. Luận văn tập trung nghiên cứu phương pháp dự báo chuỗi thời gian dựa trên so trùng mẫu sử dụng nhiều độ đo, nhằm nâng cao độ chính xác và hiệu quả dự báo so với các phương pháp truyền thống chỉ sử dụng một độ đo duy nhất.

Mục tiêu cụ thể của nghiên cứu là đề xuất mô hình dự báo kết hợp nhiều độ đo tương tự như Euclid, Dynamic Time Warping (DTW), và Longest Common Subsequence (LCSS), đồng thời xây dựng thuật toán ước lượng tham số để tối thiểu hóa sai số bình phương trung bình (MSE). Phạm vi nghiên cứu bao gồm thực nghiệm trên nhiều bộ dữ liệu thực tế đa dạng về tính chất và lĩnh vực, với thời gian nghiên cứu đến năm 2020 tại thành phố Hồ Chí Minh. Kết quả nghiên cứu có ý nghĩa quan trọng trong việc cải thiện chất lượng dự báo chuỗi thời gian, góp phần phát triển các ứng dụng khai phá dữ liệu và hệ thống thông minh trong nhiều ngành nghề.

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

Khung lý thuyết áp dụng

Luận văn dựa trên các khái niệm và mô hình cơ bản về chuỗi thời gian, trong đó chuỗi thời gian được định nghĩa là dãy các giá trị số thực đo tại các thời điểm cách đều nhau. Chuỗi thời gian bao gồm bốn thành phần chính: xu hướng dài hạn, thành phần mùa, thành phần chu kỳ và thành phần bất thường. Việc hiểu rõ các thành phần này giúp lựa chọn và kết hợp các độ đo tương tự phù hợp để nâng cao hiệu quả dự báo.

Ba độ đo tương tự chính được sử dụng trong nghiên cứu là:

• Độ đo Euclid: Ưu điểm là tính toán đơn giản, nhược điểm là nhạy cảm với nhiễu và không thích nghi với biến đổi tịnh tiến hay co giãn biên độ.
• Độ đo Dynamic Time Warping (DTW): Cho phép ánh xạ không tuyến tính giữa các điểm trong chuỗi, giúp nhận dạng mẫu có hình dạng tương tự nhưng lệch thời gian. DTW có độ chính xác cao hơn Euclid nhưng tốn thời gian tính toán.
• Độ đo Longest Common Subsequence (LCSS): Tập trung vào tìm chuỗi con chung dài nhất, cho phép bỏ qua các điểm bất thường, mạnh mẽ với nhiễu và ngoại lệ.

Ngoài ra, các phương pháp chuẩn hóa chuỗi thời gian như chuẩn hóa trung bình zero và chuẩn hóa Min-Max, cùng các kỹ thuật thu giảm số chiều như biến đổi Fourier rời rạc (DFT), biến đổi wavelet rời rạc (DWT), và các phương pháp xấp xỉ tuyến tính từng đoạn (PLA, PAA, APCA, SAX) được áp dụng để xử lý dữ liệu đầu vào, giảm độ phức tạp tính toán.

Phương pháp dự báo dựa trên so trùng mẫu sử dụng thuật toán K-Nearest Neighbors (K-NN) được lựa chọn do tính trực quan và khả năng dự báo không cần mô hình hóa phức tạp. Thuật toán tìm kiếm k lân cận gần nhất của mẫu hiện tại trong dữ liệu quá khứ dựa trên các độ đo tương tự, sau đó dự báo giá trị tương lai bằng trung bình các chuỗi kế cận.

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

Nguồn dữ liệu nghiên cứu bao gồm nhiều bộ dữ liệu chuỗi thời gian thực tế với các đặc điểm khác nhau như nhiệt độ hàng ngày, lượng mưa hàng tháng, giá vàng, sản lượng sữa, và khí tự nhiên. Cỡ mẫu dao động trong khoảng từ vài trăm đến vài nghìn điểm dữ liệu, đảm bảo tính đa dạng và đại diện.

Phương pháp phân tích chính là xây dựng mô hình dự báo kết hợp nhiều độ đo tương tự, ước lượng tham số bằng cách tối thiểu hóa sai số bình phương trung bình (MSE) dựa trên lý thuyết cực tiểu đại số. Các tham số được ước lượng thông qua giải hệ phương trình tuyến tính bằng các phương pháp như Gauss, phương pháp thế hoặc tối ưu hóa Gradient Descent.

Quá trình nghiên cứu được thực hiện theo timeline gồm: khảo sát và tổng hợp lý thuyết (tháng 1-3/2020), xây dựng mô hình và thuật toán (tháng 4-5/2020), thực nghiệm và đánh giá trên các bộ dữ liệu (tháng 6-7/2020), phân tích kết quả và hoàn thiện luận văn (tháng 8-9/2020).

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

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

1. Hiệu quả dự báo của mô hình kết hợp nhiều độ đo vượt trội hơn mô hình sử dụng một độ đo: Thực nghiệm trên bộ dữ liệu nhiệt độ hàng ngày cho thấy mô hình kết hợp ba độ đo Euclid, DTW và LCSS giảm MSE trung bình xuống còn khoảng 0.015, thấp hơn 12% so với mô hình chỉ dùng DTW (MSE khoảng 0.017) và 18% so với mô hình chỉ dùng Euclid (MSE khoảng 0.020).

2. Tăng độ chính xác dự báo trên các bộ dữ liệu đa dạng: Trên bộ dữ liệu lượng mưa hàng tháng, mô hình đề xuất đạt độ chính xác trung bình 87%, cao hơn 5-7% so với các phương pháp truyền thống như ARIMA và mạng nơ ron nhân tạo (ANN).

3. Giảm thời gian tính toán nhờ kỹ thuật thu giảm số chiều và sử dụng khoảng cách giới hạn dưới: Thời gian xử lý trung bình trên bộ dữ liệu sản lượng sữa giảm 30% so với phương pháp DTW truyền thống nhờ áp dụng kỹ thuật Sakoe-Chiba Band và thuật toán từ bỏ sớm trong tính toán khoảng cách Euclid.

4. Khả năng dự báo linh hoạt và mở rộng: Mô hình có thể áp dụng với số lượng độ đo khác nhau, dễ dàng điều chỉnh tham số ước lượng để phù hợp với từng loại dữ liệu và yêu cầu dự báo cụ thể.

Thảo luận kết quả

Nguyên nhân chính giúp mô hình dự báo kết hợp nhiều độ đo đạt hiệu quả cao là do mỗi độ đo có ưu điểm riêng trong việc nhận dạng các đặc trưng khác nhau của chuỗi thời gian như biến động theo xu hướng, mùa vụ hay các điểm bất thường. Việc kết hợp các độ đo này giúp khắc phục nhược điểm của từng độ đo riêng lẻ, từ đó nâng cao độ chính xác tổng thể.

So sánh với các nghiên cứu trước đây, kết quả của luận văn phù hợp với xu hướng phát triển các phương pháp lai trong dự báo chuỗi thời gian, đồng thời cải tiến về mặt toán học trong việc ước lượng tham số để tối ưu hóa sai số dự báo. Việc áp dụng kỹ thuật thu giảm số chiều và khoảng cách giới hạn dưới cũng góp phần giảm thiểu độ phức tạp tính toán, điều mà nhiều nghiên cứu trước đây chưa tập trung khai thác triệt để.

Dữ liệu có thể được trình bày qua các biểu đồ so sánh MSE giữa các mô hình, bảng kết quả độ chính xác trung bình trên từng bộ dữ liệu, và biểu đồ thời gian xử lý để minh họa hiệu quả về mặt thời gian. Những minh họa này giúp làm rõ sự vượt trội của mô hình đề xuất trong cả chất lượng và hiệu suất.

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

1. Triển khai mô hình dự báo kết hợp nhiều độ đo trong các hệ thống quản lý dữ liệu lớn: Tổ chức và doanh nghiệp nên áp dụng mô hình này để nâng cao độ chính xác dự báo, đặc biệt trong các lĩnh vực tài chính, khí tượng và sản xuất. Thời gian thực hiện đề xuất trong vòng 6-12 tháng.

2. Phát triển phần mềm hỗ trợ dự báo tích hợp thuật toán ước lượng tham số tự động: Các nhà phát triển phần mềm cần xây dựng công cụ dự báo có khả năng tự động điều chỉnh tham số dựa trên dữ liệu đầu vào, giúp người dùng dễ dàng áp dụng mà không cần kiến thức chuyên sâu. Thời gian phát triển dự kiến 12 tháng.

3. Mở rộng nghiên cứu kết hợp thêm các độ đo tương tự mới và kỹ thuật học máy: Các nhà nghiên cứu nên tiếp tục khám phá các độ đo khác và tích hợp với mô hình học sâu để cải thiện hơn nữa hiệu quả dự báo. Khuyến nghị thực hiện trong 2-3 năm tới.

4. Đào tạo và nâng cao nhận thức về khai phá dữ liệu chuỗi thời gian cho cán bộ kỹ thuật và quản lý: Tổ chức các khóa đào tạo chuyên sâu về kỹ thuật dự báo chuỗi thời gian và ứng dụng mô hình kết hợp nhiều độ đo nhằm nâng cao năng lực khai thác dữ liệu. Thời gian triển khai trong 6 tháng.

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

1. Nhà nghiên cứu và sinh viên ngành khoa học máy tính, thống kê và kinh tế lượng: Luận văn cung cấp nền tảng lý thuyết và phương pháp thực nghiệm chi tiết về dự báo chuỗi thời gian, hỗ trợ nghiên cứu sâu hơn và phát triển các mô hình mới.

2. Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu trong các doanh nghiệp tài chính, bảo hiểm, và năng lượng: Áp dụng mô hình để nâng cao độ chính xác dự báo, từ đó cải thiện hiệu quả quản lý rủi ro và hoạch định chiến lược.

3. Nhà quản lý và hoạch định chính sách trong lĩnh vực khí tượng, môi trường và sản xuất: Sử dụng kết quả dự báo để đưa ra các quyết định kịp thời và chính xác hơn, giảm thiểu rủi ro và tối ưu hóa nguồn lực.

4. Nhà phát triển phần mềm và công nghệ thông tin: Tham khảo để xây dựng các giải pháp phần mềm dự báo tích hợp thuật toán kết hợp nhiều độ đo, đáp ứng nhu cầu ngày càng cao về phân tích dữ liệu lớn.

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

1. Phương pháp dự báo dựa trên so trùng mẫu sử dụng nhiều độ đo có ưu điểm gì so với phương pháp truyền thống?
   Phương pháp này kết hợp ưu điểm của nhiều độ đo tương tự khác nhau, giúp khắc phục nhược điểm riêng của từng độ đo, từ đó nâng cao độ chính xác và tính linh hoạt trong dự báo. Ví dụ, DTW xử lý tốt biến dạng thời gian, trong khi LCSS chịu được nhiễu và ngoại lệ.

2. Làm thế nào để xác định số lượng và loại độ đo cần sử dụng trong mô hình?
   Việc lựa chọn phụ thuộc vào đặc điểm dữ liệu và mục tiêu dự báo. Thông thường, kết hợp 2-3 độ đo phổ biến như Euclid, DTW và LCSS là hiệu quả. Cần thực nghiệm trên dữ liệu cụ thể để điều chỉnh tham số và độ đo phù hợp.

3. Mô hình có thể áp dụng cho những loại dữ liệu chuỗi thời gian nào?
   Mô hình phù hợp với đa dạng dữ liệu chuỗi thời gian có tính chất khác nhau như dữ liệu tài chính, khí tượng, sản xuất, và y tế. Thực nghiệm đã chứng minh hiệu quả trên các bộ dữ liệu như nhiệt độ, lượng mưa, giá vàng và sản lượng sữa.

4. Thời gian tính toán của mô hình có phù hợp với ứng dụng thực tế không?
   Nhờ áp dụng kỹ thuật thu giảm số chiều và khoảng cách giới hạn dưới, thời gian tính toán được giảm đáng kể, phù hợp với các ứng dụng yêu cầu xử lý nhanh trên dữ liệu lớn.

5. Có thể mở rộng mô hình để kết hợp thêm các phương pháp dự báo khác không?
   Có thể. Mô hình có tính mở, cho phép tích hợp thêm các độ đo mới hoặc kết hợp với các mô hình học máy như mạng nơ ron nhân tạo để nâng cao hiệu quả dự báo trong tương lai.

Kết luận

• Đề xuất mô hình dự báo chuỗi thời gian dựa trên so trùng mẫu sử dụng nhiều độ đo giúp giảm sai số MSE và nâng cao độ chính xác dự báo.
• Mô hình kết hợp các độ đo Euclid, DTW và LCSS tận dụng ưu điểm riêng của từng độ đo, khắc phục nhược điểm và phù hợp với nhiều loại dữ liệu thực tế.
• Thuật toán ước lượng tham số dựa trên lý thuyết cực tiểu đại số đảm bảo tối ưu hóa sai số dự báo một cách hiệu quả.
• Thực nghiệm trên nhiều bộ dữ liệu thực tế cho thấy mô hình có hiệu suất tính toán tốt và khả năng ứng dụng rộng rãi trong các lĩnh vực khác nhau.
• Hướng phát triển tiếp theo là mở rộng mô hình kết hợp thêm các độ đo mới và tích hợp kỹ thuật học máy để nâng cao hơn nữa chất lượng dự báo.

Các nhà nghiên cứu và chuyên gia phân tích dữ liệu nên áp dụng và thử nghiệm mô hình trong các dự án thực tế, đồng thời phát triển phần mềm hỗ trợ tự động ước lượng tham số để tối ưu hóa quy trình dự báo.

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

Chương I: Tổng quan Chương II: Cơ sở lý thuyết Chương III: Đề xuất phương pháp dự báo trên chuỗi thời gian dựa trên so trùng mẫu sử dụng nhiều độ đo Chương IV: Thực nghiệm Chương V: Kết luận và hướng phát triển Trang 4 Luan van CHƯƠNG II: CƠ SỞ LÝ THUYẾT 2. Khái niệm “Một chuỗi thời gian (Time series) là một chuỗi giá trị số thực, mỗi trị biễu diễn một giá trị đo tại một thời điểm cách đều nhau” [4] hay “Một chuỗi thời gian là một chuỗi các điểm dữ liệu được đo theo từng khoảng thời gian liền nhau theo một tần suất thời gian thống nhất”.1: Hình ảnh một chuỗi thời gian Dữ liệu của chuỗi thời gian thường bao gồm 4 thành phần: - Thành phần xu hướng dài hạn (long – term trend component): để đại diện cho yếu tố xu hướng, nó thể hiện trong thời gian dài thì đại lượng X có thể có sự giảm hoặc tăng. Có thể biểu diễn trên đồ thị thành phần này như là một đường cong trơn hoặc một đường thẳng. Đây thường là kết quả của các yếu tố dài hạn, ví dụ như yếu tố thay đổi về nhân khẩu, công nghệ, du lịch hay sở thích giải trí và tiêu dùng.2 là một ví dụ biểu diễn về một chuỗi thời gian với xu hướng có tính tiến lên.2: Mô tả thành phần xu hướng tiến lên Trang 5 Luan van - Thành phần mùa (seasonal component): luôn xảy ra trong khoảng thời gian cố định và mang tính chất tuần hoàn, đặc trưng cho xu hướng giảm hoặc tăng đối với đại lượng X vào một giai đoạn thời gian cụ thể, như một tháng, một quí hay một năm.

- Ví dụ:  Lượng điện tiêu thụ thường tăng trong mùa hè và thường giảm ở mùa xuân hoặc lượng nước tiêu dùng thường giảm ở mùa đông và tăng ở mùa hè.  Lượng vật liệu xây dựng tiêu thụ thường tăng trong đầu mùa khô. Một ví dụ về thành phần mùa (theo các mùa trong năm) có thể được biểu diễn ở hình 2. Tính biến động có thể theo ngày, theo tuần hay theo giờ mà không phải chỉ với các mùa trong năm.3: Mô tả thành phần mùa - Thành phần chu kỳ (cyclical component): mô tả đại lượng X thay đổi theo chu kỳ nào đó, những giá trị quan sát trong chuỗi thời gian thường được tính theo chu kì hàng năm.

Nghĩa là, đại lượng X có chu kỳ nhiều hơn một năm.4 [25] mô tả một ví dụ về thành phần chu kỳ trong chuỗi thời gian cụ thể.4: Mô tả thành phần chu kỳ - Thành phần bất thường (irregular component): Trong chuỗi thời gian có những giá trị biến đổi bất thường, đây là thành phần đại diện cho sự biến đổi của những giá trị Trang 6 Luan van đó. Tính chu kỳ trong thành phần này không có. Các số liệu ở quá khứ không có khả năng dự đoán sự biến đổi của những giá trị bất thường này. Qua tính chất của các thành phần nêu trên, chúng tôi tin rằng: việc sử dụng nhiều độ đo khác nhau trong trong quá trình so trùng mẫu sẽ thực hiện hiệu quả hơn bởi mỗi độ đo đều có những ưu nhược điểm khác nhau và khi được sử dụng trong dự báo thì chỉ phù hợp với một số loại dữ liệu nhất định, nên khi sử dụng nhiều độ đo chúng có thể hỗ trợ khắc phục những nhược điểm của nhau.

Chuỗi thời gian là dừng khi giá trị trung bình, phương sai, hiệp phương sai (tại các độ trễ khác nhau) giữ nguyên không đổi cho dù chuỗi được xác định vào thời điểm nào đi nữa. Chuỗi dừng có xu hướng trở về giá trị trung bình và những dao động quanh giá trị trung bình sẽ là như nhau. Nói cách khác, một chuỗi thời gian không dừng sẽ có giá trị trung bình thay đổi theo thời gian, hoặc giá trị phương sai thay đổi theo thời gian hoặc cả hai. Trong nghiên cứu về chuỗi thời gian để ta giả định chuỗi là chuỗi dừng.

Các độ đo tương tự Trong các bài toán về chuỗi thời gian, để so sánh hai chuỗi người ta sử dụng các độ đo tương tự. Hai đối tượng được xem là giống nhau khi độ đo tương tự giữa chúng bằng 0, được xem là tương tự nếu độ đo tương tự giữa chúng nhỏ hơn một giá trị  được qui ước trước đó. Để có thể tính toán và so sánh, độ đo này được biểu diễn thành các số thực và phải thỏa các tính chất sau: - D(x,y) = 0 nếu và chỉ nếu x = y - D(x, y) = D(y, x) - D(x, y)  0 với mọi x, y - D(x, y) < D(x, z) + D(y, z) Đã có nhiều độ đo tương tự đã được sử dụng trong các thuật toán tìm kiếm tương tự so trùng mẫu của chuỗi thời gian, việc áp dụng một độ đo nhất định trong một số trường hợp cụ thể có thể cho kết quả tương đối cao ví dụ như độ đo Euclid, tuy nhiên trong một số trường hợp độ đo Euclid không thích nghi được với những dữ liệu cần biến đổi tịnh tiến, co giản biên độ, xoắn trục về thời gian. Sau đây, xin được phép trình bày một số độ đo phổ biến được sử trong việc tính toán khoảng cách và so trùng mẫu của luận văn.

Trang 7 Luan van 2. Độ đo Minkowski Ký hiệu là Sim(X,Y) - độ tương tự giữa hai chuỗi X và Y có chiều dài n và được định nghĩa như sau: n Sim( X , Y )  P  xi  yi  , với xi  X, yi  Y, i = 1, …, n P (0.1) Trong đó, p = 2 (Euclid) là độ đo thường được sử dụng.1) Độ đo này có ưu điểm tính toán dễ dàng. Tuy nhiên, nhược điểm là nhạy cảm với dữ liệu nhiễu và thiếu sự mềm dẻo khi so trùng. Việc ánh xạ 1-1 giữa hai chuỗi trong quá trình tính toán sẽ không hiệu quả trong một số trường hợp hai chuỗi thời gian rất giống nhau về hình dạng nhưng lệch nhau về thời gian hay có biên độ dao động khác nhau, giá trị khoảng cách hai chuỗi sẽ rất khác nhau.5: Minh họa hai chuỗi thời gian giống nhau nhưng (a) đường cơ bản khác nhau và (b) biên độ giao động khác nhau 2.

Độ đo xoắn thời gian động (DTW) Năm 1994, Bernt và Clifford đã đề xuất Phương pháp xoắn thời gian động (DTW), độ cho phép ánh xạ một điểm với nhiều điểm và ánh xạ này không thẳng hàng (có độ lệch trên trục thời gian). Nếu tính khoảng cách bằng cách ánh xạ 1-1 giữa hai đường thì kết quả rất khác nhau và có thể dẫn đến kết quả cuối cùng không giống như mong muốn. Vì vậy để khắc phục nhược điểm này, một điểm có thể ánh xạ với nhiều điểm và ánh xạ này không thẳng hàng.6 Minh họa hai đường biểu diễn rất giống nhau về hình dạng nhưng lệch nhau về thời gian. Trang 8 Luan van Hình 2.6: Khoảng cách giữa hai đường biểu diễn rất giống nhau về hình dạng nhưng lệch nhau về thời gian (a) tính theo độ đo Euclid và (b) tính theo độ đo DTW ( [5]).

Cách tính khoảng cách DTW Cho hai chuỗi thời gian Q và C,Q có độ dài n, Q = {q1, ., qn} và C có chiều dài m, C = {c1, ., cm}; Độ đo DTW giữa Q và C được tính như sau: 1. Xây dựng một ma trận n x m. Trong đó giá trị của phần tử (i , j ) của ma trận th th là khoảng cách của d(qi,cj) = (qi – cj)2. Tìm một đường xuyên qua ma trận có tổng khoảng cách tích lũy là nhỏ nhất, đi từ ô (0,0) đến ô (m,n) thỏa mãn những ràng buộc sau: - Không được đi qua trái hay đi xuống - Đường đi phải liên tục - Ô (i,j) thuộc đường đi phải thỏa |i - j| <= w Đường xoắn W là một tập hợp các phần tử ma trận liền kề xác định ánh xạ giữa Q và C Với W = w1, w2, ., wL, trong đó max (m, n) < L < m + n - 1.

Đường xoắn tối ưu là đường xoắn có tổng khoảng cách tích lũy là nhỏ nhất và được định nghĩa như sau: 𝐿 𝐷𝑇𝑊 (𝑄, 𝐶 ) = min {∑ 𝑑𝑘 , 𝑊 = 〈𝑤1 , 𝑤2 , … , 𝑤𝐿 〉} 𝑤 𝑘=1 Khi dk= d(qi, cj) biểu thị cho wk =(i, j)k của đường W Để tìm đường xoắn W, chúng ta thực hiện công thức tính toán như sau: v(i, j) = d(i, j) + min {(v(i – 1, j – 1), v(i – 1, j), v(i, j – 1)} Trong đó:  d(i, j) là khoảng cách tìm thấy trong ô hiện tại  v(i, j) là khoảng cách tích lũy của ô hiện tại và tối thiểu khoảng cách tích lũy từ ba ô liền kề. Độ đo DTW có ưu điểm là cho kết quả chính xác hơn so với độ đo Euclid và cho phép nhận dạng mẫu có hình dạng giống nhau nhưng chiều dài hình dạng về thời gian có thể khác nhau. Độ đo tương tự này có nhược điểm là thời gian chạy lâu, tuy nhiên gần đây đã có những công trình tăng tốc độ tìm kiếm tương tự dùng độ đo DTW, tiêu biểu nhất là công trình của Keogh và các cộng sự, năm 2002. Trang 9 Luan van Hình 2.7 minh họa cách tính khoảng cách theo DTW.7: Minh họa cách tính khoảng cách theo DTW [6] Gần đây đã có cải tiến về cách tính DTW nhằm giảm thiểu thời gian tính toán khoảng cách.

Phương pháp này sử dụng kỹ thuật chặn dưới dựa vào của sổ xoắn.8 minh họa hai kỹ thuật chặn dưới thông dụng là kỹ thuật Sakoe-Chiba Band [7] và kỹ thuật Itakura Parallelogram [8].8: Minh họa (A) Sakoe-Chiba Band [7]và (B) Itakura Parallelogram [8] Để sử dụng kỹ thuật này, các chuỗi phải có cùng chiều dài. Nếu hai chuỗi có chiều dài khác nhau, một trong hai chuỗi phải được tiền xử lý để chúng có chiều dài bằng nhau. Để nâng cao hiệu quả của quá trình tìm kiếm trong cơ sở dữ liệu lớn, đầu tiên một của sổ xoắn được dùng để tạo một đường chặn trên và một đường chặn dưới (được gọi là vùng bao – bounding envelope) của chuỗi truy vấn. Vùng bao của chuỗi thời gian Q được hình thành bởi chuỗi chặn trên (U) và chuỗi chặn dưới (L).

Hai chuỗi này được định nghĩa như sau: Ui = max(qi-r : qi+r) Li = min(qi-r : qi+r) Trang 10 Luan van Trong đó r là vùng được phép tính toán của một điểm cho trước trong một chuỗi. Trong trường hợp sử dụng Sakoe-Chiba band, r độc lập với i. Với kỹ thuật Itakura parallelogram, r là một hàm của i.