Chương 1 - Giới thiệu dé tai: đưa ra nguyên nhân cũng như tính cấp thiết cho việc nghiên cứu và phát triên đê tài. 21 Chương 2 - Cơ sở lý thuyết: giới thiệu những cơ sở và khái niệm nên tảng cho phương pháp luận và quá trình hiện thực của luận văn. Chương 3 - Các công trình nghiên cứu liên quan: giới thiệu các công trình lý thuyết có liên quan tới dé tài. Chương 4 - Hướng tiếp cận giải quyết van dé: giới thiệu các giai đoạn chính cho quá trình khai phá mẫu xu hướng tuần tự liên đối tượng trên cơ sở dữ liệu chuỗi thời gian.
Chương 5 - Thực nghiệm: trình bày quá trình đo đạc và so sánh kết quả khi sử dụng hai giải thuật do luận văn dé xuất. Chương 6 - Kết luận: đóng góp của luận văn và hướng nghiên cứu trong tương lai. 22 CHƯƠNG 2 : CƠ SỞ LÝ THUYET 2.1 Dữ liệu chuỗi thời gian 2.1 Time Series Một chuỗi thời gian (time series) là chuỗi trị số thực, mỗi trị biểu diễn một giá tri đo tại những thời điểm cách đều nhau [18]. Hoặc chuỗi thời gian T = tị, ứ, -» tm là một tập có thứ tự m biến mang gia tri số thực hoặc gia tri số nguyên được ghi nhận tại những thời điểm cách đều nhau [17].
Ngoài ra người ta cũng đưa ra định nghĩa về chuỗi thời gian đơn biến và chuỗi thời gian đa biến. Chuỗi thời gian đơn biến là một chuỗi thời gian chỉ chứa một quan sát được ghi nhận một cách tuần tự tại những khoảng thời gian cách đều nhau. Chuỗi thời gian đa biến là chuỗi thời gian mà trong đó tại một thời điểm ta có nhiều quan sát (biến) khác nhau.fprn¡ với [Sp<m—n+l Thông thường người ta sử dụng cửa số trượt (sliding window) để trích xuất các chuỗi con từ chuỗi thời gian T.1 cho thấy ví dụ về 3 chuỗi con A,B,C trong một chuỗi thời gian (được đánh dấu bởi mũi tên). 7 Al fi, BY C ủý \ M IỊ La’là/ Ñ/\ị VyVÍÌ\VÑ Nl ý" | \ f lề \ NM V ú4 / _ y 0 900 100% 1Š00 200 2500 Hình 2.1 Các chuỗi con trong một chuỗi thời gian [17] 23 2.3 Trùng khớp (Match) Cho một số thực dương R (thông số về phạm vi khoảng cách giúp xác định sự trùng khớp giữa 2 chuỗi con do người dùng định nghĩa) và một chuỗi thời gian T.
Biết rang T chứa một chuỗi con C bat đầu tại thời điểm p và một chuỗi con M bắt đầu tại q, néu khoảng cách D giữa 2 chuỗi nhỏ hơn hoặc bằng R, nghĩa là D(C, M) < R thì ta nói rang M là một chuỗi con trùng khớp với C và ngược lại. 2 \/ À L i + i L 1 L L 0 50 {ao 14 2M 740 cae 3 £00 450 500 Hình 2.2 M là một chuỗi con trùng khớp của chuỗi con C trong chuỗi thời gian T [17] 2.4 Trùng khớp tam thường (Trivial Match) Cho một 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 đang trùng khớp (match) với C va bắt đầu tại vị trí q. Ta định nghĩa M trùng khớp tầm thường với C nếu p = q (2 chuỗi con có cùng điểm bắt đầu) hoặc không xuất hiện một chuỗi con M' bắt đầu tại vị trí q’ sao cho D(C,M’) > R và q< q’ < phoặc p <q’ <q.3 cho thấy một vi dụ về trùng khớp tầm thường Trivial Trivial oy M atch L 1 C= 1. 1 0 50 100 150 700 350 300 150 An 4450 san Hình 2.3 Các trùng khớp tầm thường bên trái và bên phải của chuỗi C [17] 24 2.5 Trùng khớp không tầm thường (Non-trivial match) Hai chuỗi con được gọi là trùng khớp không tầm thường nếu như chúng trùng khớp nhau và được chia cắt bởi một chuỗi con khác không trùng khớp với cả 2 chuỗi trên.6 Motif Một chuỗi con (subsequence) trong chuỗi thời gian T được lặp lại ít nhất một lần trong T được xem là một motif.
Lưu ý là không cần phải trùng khớp toàn bộ (nghĩa là giỗng nhau hoàn toàn) thì mới được xem là motif. Định nghĩa này làm cho tập các motifš phải loại bỏ tương hỗ để đề phòng trường hợp các motifs có chung quá nhiều phân tử và hién nhiên trở thành một motif.2 Xứ lý dữ liệu chuỗi thời gian Đối với dữ liệu chuỗi thời gian, thông thường ta phải xem xét một số khái niệm được sử dụng để hỗ trợ cho việc so sánh và khai phá.1 Các độ đo tương tự (similarity measurement) Đối với dạng bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian, ta dùng một công thức dé tính độ tương tự giữa hai chuỗi thời gian. Độ do Euclid: [17] Cho 2 chuỗi thời gian Q = dị, do,. Un C= Cy Cạ,., Ch Ta xem mỗi chuỗi là một điểm trong không gian Euclid n chiều (với n là chiều dai của mỗi chuỗi).
Độ đo khoảng cách Euclid giữa hai chuỗi thời gian này được tính bởi công thức: 25 DQC = lề» =6,) / y NUL ` y ~ es Hinh 2.4 Tim khoang cach Euclid [18] Ưu điểm: đơn giản, dé dàng tinh, dé mở rộng cho nhiều dang bài toán khai phá dữ liệu chuỗi thời gian. Khuyết điểm: nhạy cảm với nhiễu, không tính được khi 2 chuỗi thời gian có chiều dài khác nhau hoặc biên độ dao động khác nhau [18]. Độ đo xoắn thời gian động [18] Từ 2 chuỗi thời gian X và Y, ta tính khoảng cách thông qua việc ánh xạ một điểm từ chuỗi thời gian này sang nhiều điểm của chuỗi thời gian kia và ánh xạ này không thắng hàng. Phương pháp này gọi là xoắn thời gian động (Dynamic Time Warping — DTW) do Berndt và Clifford (1996) giới thiệu Phương pháp này cho phép mở rộng hoặc thu hẹp các tín hiệu (signals) theo chiều thời gian.
Ý tưởng chính như sau: Giả sử ta có 2 chuỗi thời gian X và Y như sau: X =XI,X¿. Ym Ta cho phép sự mở rộng của từng chuỗi thời gian bang cách lặp lại các phan tử. Sau quá trình này ta được hai chuỗi mới là X’ và Y’. Độ đo Euclid sau đó được áp dụng cho hai chuỗi X’ và Y’ này: 26 = “a eee ees Hình 2.5 Tính khoảng cach theo DTW [18] Ma trận M voi mj = D(x;, yj) C1) xl x2 x3 x Hinh 2.6 Ma tran cho DTW [18] Người ta áp dung giải thuật quy hoạch động dé tính khoảng cách DWT giữa 2 chuỗi thời gian.
Đầu tiên khoảng cách con D(i, j) được tính trước rồi sau đó tiếp tục tính cho tới khi D(m.n) được tinh: Dự, J) =lx;¡— y¡ Ì+ min (DG — 1, J), DỤ — 1,J— 1), DG,j-1)) (1) Ưu điểm: kết qua tính chính xác hơn so với độ do Euclid và cho phép nhận dang mau có chiêu dài khác nhau nhưng có hình dạng giỗng nhau Khuyết điểm: thời gian chạy lâu [18]. Độ đo chuỗi con chung dài nhất (Longest Common Subsequence)[18] Phương pháp này cho phép bỏ qua những dữ liệu nhiễu khi so sánh Có thể áp dụng quy hoạch động cho bài toán tìm chuỗi con chung dài nhất 27 X =3,2,5,7,4,8, 10, 7 Y=2,5,4,7,3,10,8,6 LCS =2,5,7, 10 Độ tương tự của X và Y: Sim(X,Y) =|LCS| = 4 (Với 0< Sim(X,Y) < length ) hoặc Sim(X,Y) = lLCSI/n (Với 0< Sữm(X,Y) <1) Ưu điểm: trực quan và cho phép loại bỏ nhiễu Khuyết điểm: phải tìm ra một giải thuật và cau trúc dữ liệu phù hợp để giảm bớt không gian hao phí hoặc thời gian tìm kiếm (nếu giải quyết băng đệ qui hoặc qui hoạch động) [18].2 Chuẩn hóa dữ liệu (Data Normalization) Thông thường trước quá trình thu giảm số chiều (dimensionality reduction) hoặc rời rac hóa dữ liệu (discretization), chúng ta thường chuẩn hóa đữ liệu chuỗi thời gian trước. Lý do để ta chuẩn hóa dữ liệu là do dữ liệu đầu vào (ở đây là dữ liệu chuỗi thời gian) thường có biên độ dao động rất khác nhau va việc so sánh trực tiếp dữ liệu gốc trở nên khó khăn. Một trong những phương pháp chuẩn hóa dữ liệu thường được áp dụng là phương pháp Z-score (phương pháp chuẩn hóa dựa trên độ lệch chuẩn và giá trị trung bình).€Ñ Ngoài ra cũng có nhiều phương pháp chuẩn hóa dữ liệu khác như phương pháp chuẩn hóa theo min-max hay decimal scaling [1].3 Khai pha mẫu tuần tự phố biến 2.1 Định nghĩa Khai phá mẫu tuân tự phổ biến [1][2] là quá trình khai phá ra các sự kiện hay các chuỗi xuất hiện thường xuyên và có tính thứ tự trong cơ sở dir liệu chuỗi.
Một ví dụ tiêu biểu: “Khách hàng mua máy ảnh Canon sẽ có khuynh hướng mua thêm máy in HP trong vòng một tháng”. Van dé khai phá mẫu tuần tự pho biến được 28 Agrawal và Srikant dé xuất lần đầu năm 1995 [1] dựa trên chuỗi mua sản phẩm của khách hàng. Khai phá mẫu tuần tự được ứng dụng trong nhiều lĩnh vực như: phân tích thị trường, phân tích mẫu truy cập web, dự đoán nhu cầu mua sắm của khách hàng.Sau khi có được các mẫu tuần tự, ta sẽ tìm luật tuần tự: biéu hiện quan hệ có thể có giữa hai loạt sự kiện (sequential event) và trong đó có một loạt sự kiện xảy ra trước một loạt sự kiện khác.2 Một số khái niệm thường gap trong khai phá mẫu tuần tự pho biến Cho I= {1¡, I›,. I;} là tập tất cả items.
Tập phan tử (itemset): là một tập khác rỗng và không có thứ tự các items. Mỗi một chuỗi s được kí hiệu <e¡, es,. ,e,> sao cho sự kiện e; xay ra trước sự kiện ea, e2 xay ra trước es ,. Chiều dài của một chuỗi là số lượng item có trong chuỗi.
Chăng hạn một chuỗi S có k item được gọi là k — sequence. VD: <(AB)C> là một 3 — sequence va có kích thước là 2. Chuỗi con: chuỗi B = <b, bạ. bạụ> được gọi la chuỗi con của chuỗi ơ = <a, a>.
aạ> hay ơ là chuỗi cha của B, ký hiệu B G a, nếu tôn tại những số nguyên 1< j¡ < Jo <. <jo<m_sao cho bị © aj, bạ C aj,. Vi dụ chuỗi <(B)(AC)> là chuỗi con của <(AB)(E)(ACD}>; nhưng <(AB)(E)> không phải là chuỗi con của chuỗi <(ABE)>. Cơ sở dữ liệu chuỗi là một tập hợp các bộ dữ liệu có dạng (sid, s), trong đó sid là mã định danh của chuỗi và s là chuỗi các itemset.1 Ví dụ về cơ sở dữ liệu chuỗi [1] Sid Chuỗi (s) 10 <(AB)C(DE)> 20 <ACD(E)> 30 <(AB)(DE)> 29 Độ hỗ trợ (support): Cho cơ sở dir liệu chuỗi D, mỗi chuỗi có một chi số định danh duy nhất.
Độ hỗ trợ tuyệt đối của một mẫu tuần tự f là tong số chuỗi trong D có chứa ƒ. Độ hỗ trợ tương đối của ƒ là tỉ lệ phần trăm chuỗi trong D chứa f.