intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Dự báo chuỗi thời gian dựa trên matrix profile

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST
Báo xấu
31
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết đề xuất một phương pháp mới trong dự đoán chuỗi thời gian sử dụng matrix profile, là một vector khoảng cách của các cặp là motif hay những cặp lân cận với nhau. Với việc áp dụng thuộc tính Consecutive Neighborhood Preserving (CNP), kết quả thực nghiệm cho thấy phương pháp đề xuất có độ chính xác cao hơn và thời gian tính toán nhanh hơn các phương pháp trước đó.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Dự báo chuỗi thời gian dựa trên matrix profile

  1. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải DỰ BÁO CHUỖI THỜI GIAN DỰA TRÊN MATRIX PROFILE Trần Thị Dung1, Trần Phong Nhã1, Bùi Ngọc Dũng2* Phân hiệu tại Thành phố Hồ Chí Minh, Trường Đại học Giao thông vận tải, 1 Số 450-451 Lê Văn Việt, Phường Tăng Nhơn Phú A, Quận 9, Thành phố Hồ Chí Minh 2 Khoa Công nghệ thông tin, Trường Đại học Giao thông vận tải, Số 3 Cầu giấy, Hà Nội * Tác giả liên hệ: Email: dnbui@utc.edu.vn. Tóm tắt. Dự báo chuỗi thời gian là một lĩnh vực đang được các nhà khoa học quan tâm do đó có nhiều ứng dụng trong thực tế. Đã có nhiều phương pháp được đề xuất trong bài toán dự báo chuỗi thời gian như: dự báo tuyến tính, mô hình tự hồi quy, mô hình trung bình trượt, mô hình mạng neural nhân tạo, mô hình Markov ẩn. Tuy nhiên các phương pháp đó có nhược điểm là thời gian tính toán lâu và không có nhiều trường hợp thực nghiệm để so sánh kết quả tối ưu. Trong bài báo này, chúng tôi đề xuất một phương pháp mới trong dự đoán chuỗi thời gian sử dụng matrix profile, là một vector khoảng cách của các cặp là motif hay những cặp lân cận với nhau. Với việc áp dụng thuộc tính Consecutive Neighborhood Preserving (CNP), kết quả thực nghiệm cho thấy phương pháp đề xuất có độ chính xác cao hơn và thời gian tính toán nhanh hơn các phương pháp trước đó. Từ khóa: chuỗi thời gian, motif, dự báo chuỗi thời gian, Consecutive Neighborhood Preserving; 1. ĐẶT VẤN ĐỀ Dự báo chuỗi thời gian là một nhu cầu không thể thiếu cho những hoạt động của con người trong bối cảnh bùng nổ thông tin. Việc dự báo sẽ cung cấp những cơ sở cần thiết cho các hoạch định và có thể nói rằng, nếu không có khoa học dự báo thì những dự định tương lai của con người vạch ra sẽ không có sự thuyết phục đáng kể. Các ứng dụng của dự báo chuỗi thời gian được sử dụng trong các lĩnh vực: tài chính để dự báo giá chứng khoán [1], dự báo kinh doanh xăng dầu [2], dự báo tuyển sinh đại học [3], dự báo dân số [3]. Đã có nhiều phương pháp dự báo chuỗi thời gian được các nhà nghiên cứu đề xuất những năm gần đây. Năm 2009, Jiang đề xuất phương pháp dự báo chuỗi thời gian chứng khoán dựa vào thông tin motif [4]. Năm 2007, Lora sử dụng kỹ thuật lân cận gần nhất có trong số để dự báo dữ liệu [5]. Năm 2015, cách tiếp cận mới dựa trên đại số gia tử theo ngữ nghĩa trong bài toán dự báo chuỗi thời gian mờ đã được Hiếu cùng các cộng sự giới thiệu [6]. Năm 2016, Tùng và các cộng sự đã sử dụng chuỗi thời gian mờ theo tiếp cận đại số gia tử để dự báo chuỗi thời gian [7]. -680-
  2. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải Phương pháp dự báo bằng matrix profile là một phương pháp mới áp dụng cho chuỗi thời gian. Đây là phương pháp tìm lân cận gần nhất của mỗi chuỗi con trong chuỗi thời gian. Dựa vào đặc tính lân cận gần nhất, ta có thể đưa ra dự đoán về các giá trị tiếp diễn trong chuỗi thời gian. Phương pháp được thử nghiệm trên tập dữ liệu neuroscience cho kết quả tốt hơn về độ chính xác và thời gian. 2. PHƯƠNG PHÁP DỰ ĐOÁN CHUỖI THỜI GIAN 6.1. Nền tảng lý thuyết 2.1.1. Chuỗi thời gian: Nếu T là một chuỗi thời gian thì T=(t1, t2,…,tn) gồm tập hợp n số có giá trị thực theo thời gian [8]. 2.1.2. Chuỗi con: Cho một chuỗi thời gian T = (t1, t2…, tn), một chuỗi con có chiều dài n của T là một chuỗi Ti, n = (ti, ti+1,…, ti+n-1) với 1≤ i ≤ m-n+1 [8]. 2.1.3. Các định nghĩa về matrix profile Định nghĩa 1: Một Matrix distances Di tương ứng với chuỗi con Ti, m và chuỗi thời gian T là một vectơ của khoảng cách Euclide giữa một chuỗi con đã cho Ti, m và mỗi chuỗi con trong chuỗi thời gian T. Hoặc Di = [di, 1, di, 2,..., di, n-m + 1], trong đó di, j (1≤ j ≤ n - m + 1) là khoảng cách giữa Ti, m và Tj, m [9]. Định nghĩa 2: Một Matrix profile P của chuỗi thời gian T là một vector của khoảng các Euclide giữa mỗi chuỗi con của T và lân cận gần nhất trong T, khái niệm lân cận gần nhất có nghĩa là hai cặp chuỗi con có khoảng cách nhỏ nhất so với các chuỗi con khác. Hay, P = [min(D1), min(D2),…,min(Dn-m+1)], trong đó Di (1 ≤ i ≤ n-m+1) là Matrix distances Di tương ứng với truy vấn Ti,m và chuỗi thời gian T [9]. Trong Hình 1 thể hiện mối quan hệ giữa khoảng cách ma trận, Matrix distances và Matrix profile. Mỗi thành phần của ma trận khoảng cách di,j là khoảng cách giữa Ti,m và Tj,m (1 ≤ i, j ≤ n-m+1) trong chuỗi thời gian T. Hình 1. Mối quan hệ giữa khoảng cách ma trận, Matrix distances và Matrix profile ([9]). Chỉ số i trong Matrix profile P nói chúng ta khoảng cách Euclide giữa chuỗi con Ti, m với lân cận gần nhất trong chuỗi thời gian T. Tuy nhiên, nó không nói lên vị trí -681-
  3. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải của các lân cận gần nhất, vì vậy khái niệm chỉ số Matrix profile được đưa ra: Định nghĩa 3: Matrix profile index I của chuỗi thời gian T là một vector các số nguyên: I= [I1, I2, … In-m+1], trong đó Ii=j nếu di,j = min(Di) [9]. Hình 2. Ví dụ về Matrix profile index của môt chuỗi thời gian ([9]). Vị trí giá trị tối thiểu trong mỗi cột được lưu trữ cùng với Matrix profile index. 6.2. Thuật toán Thuật toán SCRIMP++ là thuật toán được kết hợp 2 thuật toán: PreSCRIMP và SCRIMP. Thuật toán PreSCRIMP là thuật toán thuộc phương pháp tìm kiếm motif gần đúng, nó có độ phức tạp là O(n2logn/s). Thuật toán SCRIMP là thuật toán thuộc phương pháp tìm kiếm chính xác và nó có độ phức tạp O(n2). Thuật toán SCRIMP sử dụng thuật toán PreSCRIMP làm tiền xử lý chuỗi thời gian, nó có khả năng phát hiện motif trong chuỗi thời gian và nó chỉ tìm ra được Matrix Profile gần đúng. Từ Matrix Profile gần đúng đó sẽ làm input cho thuật toán SCRIMP để tìm ra được Matrix Profile chính xác. Đó chính là ý tưởng của thuật toán SCRIMP++ [9]. Đối với những bài toán có dữ liệu xử lí lớn thì giải thuật SCRIMP++ vẫn có thể thực hiện được, ta có thể dừng bất kì thời điểm nào để tìm ra motif mà không nhất thiết phải duyệt hết chuỗi thời gian. 6.2.1. Thuật toán SCRIMP: Trước khi đi vào thuật toán SCRIMP ta xem lại công thức chuẩn hóa z trong khoảng cách distance di,j của hai chuỗi con Ti,m và Tj,m với công thức sau đây: di,j= (1) Trong đó: + m là độ dài chuỗi con + Qi,j là chập các điểm trong Ti,m và Tj,m + μi là giá trị trung bình của Ti,m + μj là giá trị trung bình của Tj,m + σi là độ lệch chuẩn của Ti,m + σj là độ lệch chuẩn của Tj,m Trong bài toán này, chuỗi thời gian T sẽ dùng một cửa sổ trượt lần lượt các điểm với chiều dài m (m chính là chiều dài chuỗi con) và sẽ thực hiện chuẩn hóa mỗi lần trượt. Việc chuẩn hóa ngay trong bước trượt lấy chuỗi con sẽ giúp tiết kiệm thời gian -682-
  4. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải hơn, vì ta bỏ được một vòng lặp đề cắt ra chuỗi con, lưu trữ xuống và chuẩn hóa từng chuỗi con. Thuật toán SCRIMP được trình bày như trong Bảng 1 dưới đây: Bảng 1. Thuật toán SCRIMP[9]. Thuật toán SCRIMP Input: Một chuỗi thời gian T và một độ dài chuỗi con m Output: Matrix profile P và matrix profile index I của chuỗi thời gian T 1 n  độ dài chuỗi thời gian T 2 Tính µ, σ của chuỗi thời gian T với độ dài chuỗi con là m 3 Khởi tạo giá trị ban đầu: P infs, I ones 4 Orders RandPerm(m/4+1:n-m+1) // đánh giá giá trị order ngẫu nhiên 5 for k in Orders 6 for i 1 to n-m+2-k 7 if i=1 do q DotProduct(T1,m , Tk,m) 8 else q q-ti-1ti+k-2 + ti+m-1ti+k+m-2 9 end if 10 d CalculateDistance(q, µi, σi, µi+k-1, σi+k-1) 11 if d
  5. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải 3 các chuỗi con thứ 11, 12, 13, 14 tương ứng với các chuỗi con là lân cận gần nhất của nó với các chuỗi thứ 136, 137, 138, 139. Hình 3. Thuộc tính Consecutive Neighborhood Preserving (CNP) ([9]). Dựa vào thuộc tính CNP, ý tưởng đề ra thuật toán tiền xử lý preSCRIMP để tìm ra một matrix profile xấp xỉ với thời gian chạy nhanh hơn rất nhiều so với thuật toán SCRIMP. Đối với mỗi lần lấy mẫu, ta tìm lân cận gần nhất của mẫu. Giả sử Ti,m là một chuỗi con được lấy mẫu và Tj,m là lân cận gần nhất của chuỗi con Ti,m. Theo như CNP thì chuỗi Ti+k,m có thể có lân cận gần với nó là chuỗi con Tj+k,m ( k= -s+1, -s+2, ..., -2, - 1, 1, 2, ..., s-2, s-1) và s là khoảng thời gian lấy mẫu. Trong thuật toán preSCRIMP [9] để tìm ra được matrix profile và matrix profile index, nó sử dụng thuật toán để tính distance profile đó là thuật toán MASS (Mueen’s ultra-fast Algorithm for Similarity Search). Thuật toán MASS không chỉ trả về khoảng cách của các chuỗi con gần nó nhất mà còn trả về khoảng cách của mọi chuỗi con. Bảng 2. Thuật toán preSCRIMP [9]. Thuật toán PreSCRIMP Input: Một chuỗi thời gian T, một độ dài chuỗi con m và một khoảng lấy mẫu s Output: Matrix profile P và matrix profile index I của chuỗi thời gian T 1 n  độ dài chuỗi thời gian T, P infs, I ones 2 Tính µ, σ của chuỗi thời gian T với độ dài chuỗi con là m 3 for i RandPerm(1: s : (n-m+1)) do 4 seqTi,m 5 d=MASS (T, seq) 6 P,I ElementWiseMin(D, P, i) 7 Pi, Ii min(D) 8 jIi 9 qCalculateDotProduct(Pi, µi, σi, µj, σj), q’=q 10 for k 1 to min(s-1, n-m+1-max(i,j)) 11 qq-ti+k-1tj+k-1+ti+k+m-1tj+k+m-1 12 d CalculateDistance(q, µi+k, σi+k, µj+k, σj+k) 13 if d
  6. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải 16 q q’ 17 for k 1 to min(s-1, i-1, j-1) do 18 q q-ti-k+mtj-k+m+ti-ktj-k 19 d CalculateDistance(q, µi-k, σi-k, µj-k, σj-k) 20 if d
  7. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải 7. THỬ NGHIỆM Bộ dữ liệu Neuroscience là bộ dữ liệu về khoa học thần kinh của con người. Được các nhà khoa học nghiên cứu và giới thiệu trên nhiều nguồn tài liệu như: sách, báo, website. Bộ dữ liệu Neuroscience được ứng dụng nhiều trong lĩnh vực y khoa như: dự báo chấn thương sọ não, phát hiện ung thư não,... . Đã có một số nghiên cứu về việc xử lý và phân tích dữ liệu này để ứng dụng trong thực tế một cách hiệu quả hơn [11]. Chạy thực nghiệm trên dữ liệu Neuroscience ở các trường hợp cho kết quả như các hình dưới đây: + Trường hợp 1: Độ dài chuỗi thời gian: 512 điểm, độ dài chuỗi con: 80 điểm, độ dài chuỗi dự đoán: 20 điểm. Bảng 3. Kết quả thực nghiệm trường hợp 1. Điểm Giá trị thật Giá trị dự đoán Chênh lệch 513 -55,66406374 -55,32837038 0,33569336 514 -55,69458132 -55,02319459 0,67138673 515 -55,66406374 -54,80957154 0,8544922 516 -55,84716922 -54,68750123 1,15966799 517 -55,93872195 -54,56543091 1,37329104 518 -55,69458132 -54,59594849 1,09863283 519 -55,66406374 -54,80957154 0,8544922 520 -56,21338016 -54,80957154 1,40380862 521 -56,21338016 -54,62646607 1,58691409 522 -56,18286258 -54,65698365 1,52587893 523 -56,24389774 -55,26733522 0,97656252 524 -56,48803837 -55,38940554 1,09863283 525 -56,42700321 -55,48095828 0,94604493 526 -56,42700321 -55,41992312 1,00708009 527 -56,51855595 -55,48095828 1,03759767 528 -56,70166142 -55,57251101 1,12915041 529 -56,64062627 -55,78613406 0,85449221 530 -56,70166142 -56,12182743 0,57983399 531 -56,97631963 -56,42700322 0,54931641 532 -57,22046026 -56,51855596 0,7019043 Theo như kết quả trong Bảng 3, sự chênh lệch giá trị giữa chuỗi dự đoán và chuỗi -686-
  8. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải thật không quá lớn. Chênh lệch lớn nhất trong trường hợp này xấp xỉ 1,5. Theo dõi biểu đồ được thể hiện trong Hình 4 dưới đây để quan sát sự chênh lệch (Chuỗi màu xanh là chuỗi thực tế và chuỗi màu đỏ là chuỗi dự đoán). Hình 4. Kết quả chuỗi dự đoán thực nghiệm trong trường hợp 1. + Trường hợp 2: Độ dài chuỗi thời gian: 1024 điểm, độ dài chuỗi con: 100 điểm, độ dài chuỗi dự đoán: 25 điểm. Bảng 4: Kết quả thực nghiệm trường hợp 2 Điểm Giá trị thật Giá trị dự đoán Chênh lệch 1025 -55,7556 -56,0913 0,335693 1026 -55,4504 -55,8472 0,396729 1027 -55,2979 -55,4504 0,152588 1028 -55,1453 -55,2368 0,091553 1029 -55,0232 -54,9011 0,12207 1030 -54,8706 -54,5959 0,274658 1031 -54,8706 -54,657 0,213623 1032 -54,7791 -54,5959 0,183105 1033 -54,5654 -54,4739 0,091553 1034 -54,5654 -54,4434 0,12207 1035 -54,7485 -54,6875 0,061035 1036 -54,5959 -54,718 0,12207 1037 -54,1992 -54,3518 0,152588 1038 -54,1687 -54,0161 0,152588 -687-
  9. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải 1039 -53,894 -54,1077 0,213623 1040 -53,5584 -53,9246 0,366211 1041 -53,1616 -53,5278 0,366211 1042 -52,948 -53,6499 0,701904 1043 -52,9175 -53,7415 0,823975 1044 -52,7649 -53,894 1,12915 1045 -52,8564 -53,9856 1,12915 1046 -53,009 -54,1382 1,12915 1047 -53,0701 -54,1992 1,12915 1048 -52,948 -54,2603 1,312256 1049 -53,1616 -54,3213 1,159668 Theo như kết quả trong Bảng 4, chuỗi dự đoán và chuỗi thực tế có sự chênh lệch không quá lớn. Sự chênh lệch lớn nhất là 1,15. Biểu đồ trong Hình 5 thể hiện trực quan kết quả thực nghiệm. Hình 5. Kết quả chuỗi dự đoán thực nghiệm trong trường hợp 2 + Trường hợp 3: Độ dài chuỗi thời gian: 2048 điểm, độ dài chuỗi con: 40 điểm, độ dài chuỗi dự đoán: 10 điểm. Bảng 5. Kết quả thực nghiệm trường hợp 3. Điểm Giá trị thật Giá trị dự đoán Chênh lệch 2049 -57,58667121 -57,5866712 0,00000001 -688-
  10. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải 2050 -57,7392591 -57,7392591 0 2051 -57,70874152 -57,83081183 0,12207031 2052 -57,43408332 -57,61718878 0,18310546 2053 -57,76977668 -57,83081183 0,06103515 2054 -58,10547005 -58,31909309 0,21362304 2055 -58,01391731 -58,31909309 0,30517578 2056 -57,80029426 -58,25805794 0,45776368 2057 -57,891847 -58,25805794 0,36621094 2058 -57,80029426 -58,10547004 0,30517578 Hình 6. Kết quả chuỗi dự đoán thực nghiệm trong trường hợp 3. Thực nghiệm ở trường hợp số 3, với độ dài chuỗi dự đoán là 10 điểm thì sự chênh lệch giữa chuỗi thực tế và chuỗi dự đoán cũng không có quá nhiều sự khác biệt. Kết quả được thể hiện trong Bảng 5 và Hình 6. 8. KẾT LUẬN Qua các trường hợp thực nghiệm cho thấy, kết quả dự đoán cho giá trị gần bằng giá trị thực. Các xu hướng tăng giảm trên chuỗi thời gian ở kết quả dự đoán tương tự giá trị thật. Từ đó cho thấy, phương pháp tìm motif bằng matrix profile để dự đoán có kết quả tương đối tốt và có thể áp dụng được trong thực tế. Hướng phát triển tiếp theo có thể là dựa vào các chuỗi con khác nhau để dự đoán chuỗi thời gian chứ không xét một chuỗi con. -689-
  11. Hội nghị Khoa học công nghệ lần thứ XXII Trường Đại học Giao thông vận tải LỜI CẢM ƠN Nghiên cứu này được tài trợ bởi Trường đại học Giao thông vận tải và Phân hiệu Trường đại học Giao thông vận tải tại thành phố Hồ Chí Minh trong khuôn khổ đề tài mã số T2020-PHII-003. TÀI LIỆU THAM KHẢO [1]. N. M. Dũng, “Dự báo giá chứng khoán bằng phương pháp chuỗi thời gian,” Trường đại học Khoa học tự nhiên, Hà Nội, 2014. [2]. T. V. T. Em, “Nghiên cứu ứng dụng chuỗi thời gian trong việc dự báo kinh doanh xăng dầu”. [3]. N. V. Tính and N. C. Điều, “Dự báo chuỗi thời gian mờ dựa trên nhóm quan hệ mờ phụ thuộc thời gian và tối ưu bầy đàn,” in Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)”, Cần Thơ, 2016. [4]. Z. Q. Jiang and W. J. Xie, “ Trading networks, abnormal motifs and stock manipulation”, Quantitative Finance Letters, 2013. [5]. A. T. Lora, J. M. R. Santos, A. G. Expósito and J. L. M. Ramos, “ Electricity Market Price Forecasting Based onWeighted Nearest Neighbors Techniques”, IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 22, NO. 3, AUGUST 2007. [6]. N. D. Hiếu, V. N. Lân và N. C. Hồ, “Dự báo chuỗi thời gian mờ dựa trên ngữ nghĩa”, Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 [7]. H. Tùng, N. Đ. Thuân và V. M. Lộc, “Phương pháp dự báo chuỗi thời gian trên chuỗi thời gian mờ theo tiếp cận đại số gia tử”, Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX , Cần Thơ, 2016, 10.1562. [8]. A. Mueen, E. Keogh , Q. Zhu, S. Cash and B. Westover, "Exact Discovery of Time Series Motifs".University of California. [9]. Y. Zhu, C. M. Yeh, Z. Zimmerman, K. Kamgar and E. Keogh, "Matrix Profile XI: SCRIMP++: Time Series Motif Discovery at Interactive" in IEEE International Conference on Data Mining (ICDM), 2018. [10]. Y. Zhu and Z. Zimmerman, "Matrix Profile II: Exploiting a Novel Algorithm and GPUs to Break the One Hundred Million Barrier for Time Series Motifs and Joins", EEE ICDM, 2016. [11]. A. Bhagchandani, D. Bhatt and M. Chopade, “Various Big Data Techniques to Process and Analyze Neuroscience Data”, Proceedings of the 12th INDIACom; INDIACom-2018; IEEE Conference ID: 42835 2018 5th International Conference on “Computing for Sustainable Global Development”, 14th - 16th March, 2018. -690-
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí
65 tài liệu
2428 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
7=>1