Chương 1 TỔNG QUAN 1 Lý do chọn đề tài Cuộc cách mạng công nghiệp lần thứ IV đã và đang mang lại nhiều kết quả cũng như thách thức lớn cho ngành khoa học máy tính nói chung và lĩnh vực khai phá dữ liệu nói riêng, đặc biệt là dữ liệu có yếu tố thời gian như: tỷ giá ngoại tệ, giá vàng, chỉ số chứng khoán, dự báo thời tiết, thiên văn học, đo mực nước, điện tâm đồ,… Một cuộc khảo sát về các hướng nghiên cứu và các thách thức lớn trong lĩnh vực khai phá dữ liệu và học máy được thực hiện bởi Wu và Yang[22] năm 2006 đã cho ra kết quả 10 hướng nghiên cứu chính, trong đó nghiên cứu về khai phá dữ liệu được xếp thứ 3 trong 10 hướng nghiên cứu thách thức và quan trọng nhất. Vì vậy khai phá dữ liệu chuỗi thời gian đã và đang thu hút sự quan tâm của nhiều nhà nghiên cứu trên thế giới. Hiện nay có rất nhiều bài toán điển hình để khai phá dữ liệu chuỗi thời gian như: Gom cụm, Lập chỉ mục, Phân lớp, Phát hiện Motif, Phát hiện bất thường,. Có rất nhiều lĩnh vực đã và đang ứng dụng rộng rãi khai phá dữ liệu chuỗi thời gian như: chứng khoán - tài chính – ngân hàng, y học, thiên văn học, địa chất, côn trùng học … Các lĩnh vực nghiên cứu như y học hay tài chính, ngân hàng, … thường yêu cầu về độ chính xác cao.
Những chuỗi bất thường trên các dữ liệu chuỗi thời gian thường ảnh hưởng nhiều đến các kết quả khai phá dữ liệu. Cho nên việc xác định các chuỗi bất thường trên dữ liệu chuỗi thời gian đóng vai trò quan trọng và thường được dùng như các bước tiền xử lý cho những bài toán khai phá dữ liệu chuỗi thời gian. Với những phân tích trên, bài toán phát hiện chuỗi bất thường đã thu hút được sự quan tâm đáng kể của cộng đồng nghiên cứu từ thập niên 1980. Các nhóm nghiên cứu [9], [16], [11], [17], [24], [27], [1], [2], [3], [5] đã định nghĩa nhiều loại chuỗi bất thường khác nhau như outlier, anomaly, unusual, discord, … và đã 1 đề xuất nhiều phương pháp phát hiện chuỗi bất thường.
Trong đó, phương pháp phát hiện chuỗi bất thường discord (discord discovery) được Keogh et al. [6] giới thiệu từ năm 2005 và gần đây được các nhóm [21], [13], [20], [19], [14] tập trung nghiên cứu. 2 Mục đích đề tài - Nghiên cứu lý thuyết và đánh giá bằng thực nghiệm giải thuật phát hiện bất thường trên chuỗi thời gian. 3 Nhiệm vụ đề tài - Nghiên cứu về chuỗi thời gian và bài toán phát hiện bất thường trên chuỗi thời gian.
- Nghiên cứu phát hiện bất thường trên chuỗi thời gian sử dụng ma trận khoảng cách. - Nghiên cứu cách tính ma trận khoảng cách trong không gian thu giảm. - Nghiên cứu cách tính ma trận khoảng cách trong không gian gốc. 4 Đối tượng và phạm vi nghiên cứu 4.1 Đối tượng nghiên cứu Dữ liệu chuỗi thời gian và các phương pháp phát hiện bất thường trên dữ liệu chuỗi thời gian.2 Phạm vi nghiên cứu Phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào ma trận khoảng cách.
5 Cách tiếp cận và phương pháp nghiên cứu Tổng hợp các kết quả nghiên cứu liên quan trước đây. Đưa ra đánh giá thực nghiệm để kiểm tra kết quả. 6 Ý nghĩa thực tiễn của đề tài Hiện nay việc nghiên cứu phát hiện bất thường được ứng dụng trong nhiều lĩnh vực: chăm sóc sức khỏe, năng lượng, chứng khoán, tài chính, sản xuất, bảo mật … vì vậy đây là bài toán quan trọng được rất nhiều nhà nghiên cứu quan tâm. Do đó qua nghiên cứu này sẽ tạo thêm tiền đề cho những nghiên cứu tiếp theo về các bài toán phát hiện bất thường trong khai phá dữ liệu chuỗi thời gian.
2 Chương 2 CÁC KIẾN THỨC CƠ SỞ Chương này sẽ trình bày các lý thuyết cơ sở liên quan đến nội dung được nghiên cứu trong luận văn bao gồm: chuỗi thời gian, cửa sổ trượt, so trùng mẫu, các độ đo tương tự, thu giảm số chiều, rời rạc hóa chuỗi thời gian.1 Các kiến thức cơ bản 2.1 Chuỗi thời gian Chuỗi thời gian T = t1, t2, … tn là một tập theo thứ tự các biến giá trị thực chiều dài n [4]. Ví dụ về chuỗi thời gian là: lưu lượng mưa hàng năm ở miền nam Việt Nam, kết quả điện tâm đồ, thời tiết… Hình 2.1: Minh họa về chuỗi thời gian biểu diễn kết quả điện tâm đồ - ECG [29] 2.2 Chuỗi con Cho một chuỗi con Ti,m của chuỗi thời gian T = (t1, t2…, tn), là một tập hợp con liên tục các giá trị của T có độ dài m, bắt đầu từ vị trí i.3 Cửa sổ trượt Cho một dữ liệu chuỗi thời gian T có chiều dài n, để xác định được chuỗi con có chiều dài m, ta dùng một cửa sổ trượt có kích thước m trượt qua từng điểm từ trái sang phải trên chuỗi T để xác định mỗi chuỗi con Q.2: Mô tả cửa sổ trượt trên chuỗi thời gian T [26] 2.4 So trùng mẫu Cho một số thực R (gọi là phạm vi và do người dùng định nghĩa) và một dữ liệu chuỗi thời gian T chứa một chuỗi con C bắt đầu tại vị trí p và một chuỗi con M bắt đầu tại vị trí q, nếu hàm tính khoảng cách từ C đến M ký hiệu D(C, M) ≤ R (ta dùng công thức tính khoảng cách euclid để tính toán khoảng cách giữa 2 chuỗi con) thì ta nói là chuỗi con M khớp được với chuỗi con C [26].3: Trùng khớp giữa hai chuỗi con C và M được trích từ chuỗi T [26] 2.1 So trùng tầm thường Cho một số thực dương R và một chuỗi thời gian T. Một chuỗi con Ci của T bắt đầu tại vị trí i và một chuỗi con Cj của T bắt đầu tại vị trí j, nếu DIST(Ci , Cj) ≤ R thì Cj được gọi là chuỗi con tương tự của Ci. Các chuỗi con tương tự nhất với một chuỗi con Ci là các chuỗi con bắt đầu tại các 4 vị trí lệch một hay hai điểm về bên trái hay bên phải so với vị trí bắt đầu của chuỗi con Ci.
Có nghĩa là chuỗi con mới lệch một khoảng so với chuỗi con cũ và hai chuỗi con này có chung một đoạn giá trị. Các trường hợp này được gọi là so trùng tầm thường.4: So trùng tầm thường của 2 chuỗi con trong chuỗi thời gian T [26] 2.2 So trùng không tầm thường Cho chuỗi thời gian T có chiều dài n, chuỗi C và M có chiều dài m và là chuỗi con của chuỗi thời gian T. Chuỗi C bắt đầu tại vị trí p, chuỗi M bắt đầu tại vị trí q. Ta nói chuỗi con M và chuỗi con C so trùng không tầm thường nếu |p-q| ≥ m.5 Các độ đo tương tự Đối với bài toán phát hiện bất thường trên dữ liệu chuỗi thời gian, bài toán tìm kiếm tương tự, gom cụm, phân loại trên dữ liệu thời gian thì dữ liệu chuỗi thời gian là dãy các số thực T=t1, t2,…tn.
Đối với những bài toán này đòi hỏi chúng ta phải định nghĩa một độ đo tương tự giữa các cặp chuỗi thời gian với nhau. Cho 2 chuỗi thời gian Q và C bất kỳ. Ta cần tính độ đo tương tự Dist(Q,C) của hai chuỗi thời gian này. Để tính toán chính xác thì các độ đo cần thỏa một số tính chất cơ bản sau: - Dist(Q,C) = 0 nếu và chỉ nếu Q = C - Dist(Q,C) = Dist(C,Q) - Dist(Q,C) ≥ 0 với mọi Q, C - Dist(Q,C) < Dist(Q, Z) + D(C, Z) 5 2.1 Minkowski Hầu hết các công trình nghiên cứu trên dữ liệu chuỗi thời gian đều dựa trên độ đo Minkowski để tính khoảng cách (hay mức độ tương tự) giữa hai chuỗi con.
Công thức tính khoảng cách Minkowski được định nghĩa như sau: 𝑝 𝐷𝑖𝑠𝑡(𝑄, 𝐶) = √∑𝑛𝑖=1(𝑞𝑖 − 𝑐𝑖 )𝑝 ) (2.1) với qi ∈ Q, ci ∈ C, i = 1, …, n Khi p = 1 ta có khoảng cách Manhattan Khi p = 2 ta có khoảng cách Euclid Khi p = ∞ ta có khoảng cách Max Ở công thức trên thì giá trị của p có thể chọn bất kỳ, nhưng thông thường trong các nghiên cứu về chuỗi dữ liệu thời gian thì thường sử dụng độ đo Euclid vì nó đơn giản, dễ thực hiện và là khoảng cách hình học trong không gian đa chiều với độ chính xác chấp nhận được[7]. Ưu điểm: + Tính toán nhanh, đơn giản. + Sử dụng trong nhiều bài toán khai phá dữ liệu chuỗi thời gian khác như gom cụm, phân lớp, phát hiện bất thường trên dữ liệu chuỗi thời gian. + Độ đo Minkowski thỏa mãn bất đẳng thức tam giác nên có thể hỗ trợ việc lập chỉ mục dữ liệu, giảm thời gian phát hiện bất thường trên dữ liệu chuỗi thời Nhược điểm: + Nhạy cảm với nhiễu + Các chuỗi thời gian có độ dài như nhau + Đối với dữ liệu có đường căn bản khác nhau thì thuật toán này chưa xử lý tốt (Hình 2.5 a) +Không thích hợp khi dữ liệu có biên độ dao động khác nhau.: Minh họa hai chuỗi thời gian tương đồng Hình 2.
Để khắc phục một số nhược điểm của độ đo này thì ta có thể sử dụng phương pháp chuẩn hóa dữ liệu (Data normalization). Hai phương pháp chuẩn hóa dữ liệu đang được sử dụng hiện nay là: Chuẩn hóa trung bình Zero [26]: - Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức 𝑄[𝑖]− 𝑚𝑒𝑎𝑛(𝑄) Q’[i] = (2.2) 𝑣𝑎𝑟(𝑄) Với mean(Q) là giá trị trung bình và var(Q) là độ lệch chuẩn của Q. Trong trường hợp không biết được giá trị lớn nhất và nhỏ nhất của tập dữ liệu hay có những giá trị cá biệt thì phương pháp này có thể được áp dụng. Chuẩn hóa Min-Max [26]: Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức 𝑄[𝑖]−𝑀𝑖𝑛𝑜𝑙𝑑 𝑄’[𝑖] = (𝑀𝑎𝑥𝑛𝑒𝑤 − 𝑀𝑖𝑛𝑛𝑒𝑤 ) + 𝑀𝑖𝑛𝑛𝑒𝑤 (2.3) 𝑀𝑎𝑥𝑜𝑙𝑑 −𝑀𝑖𝑛𝑜𝑙𝑑 Với Minold và Maxold là giá trị nhỏ nhất và lớn nhất của chuỗi Q ban đầu.
Minnew và Maxnew là giá trị nhỏ nhất và lớn nhất của chuỗi Q’ là chuỗi sau khi được chuẩn hóa. Chuẩn hóa Min-Max đảm bảo được mối quan hệ giữa các giá trị của dữ liệu ban đầu nhưng phương pháp này sẽ gặp phải lỗi ngoài giới hạn nếu một giá trị ban đầu vào tương lai nằm ngoài đoạn giá trị [Min – Max] ban đầu.2 Độ đo xoắn thời gian động Khi hai đường biểu diễn là hai mẫu cần so sánh không giống nhau hoàn toàn nhưng hình dạng biển đổi giống nhau thì việc sử dụng các khoảng cách so sánh 7 từng cặp điểm 1-1 để tìm ra độ tương tự giữa hai mẫu thì không phù hợp.