chương 1 – Giới thiệu đề tài, cấu trúc luận văn còn có các chương khác sau: 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 nghiên cứu liên quan đến nội dung mà đề tài đang quan tâm nghiên cứu, bao gồm các kỹ thuật về khai phá mẫu phổ biến, khai phá mẫu phổ biến gia tăng, v. Chương 4 – Hướng tiếp cận giải quyết vấn đề Chương 5 – Thực nghiệm: trình bày quá trình thực hiện thực nghiệm với những đề xuất của luận văn. 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.
15 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT 2. Dữ liệu chuỗi thời gian 2. Chuỗi thời gian (Time Series) Chuỗi thời gian (time series) là chuỗi trị số thực, mỗi trị biểu diễn một giá trị đo tại những thời điểm cách đều nhau [1]. Dữ liệu chuỗi thời gian thường có kích thước rất lớn và được ứng dụng rộng rãi trong các lãnh vực khác nhau.1 Ví dụ về chuỗi thời gian (time series) [14] Ngoài ra, cũng có những định nghĩa về chuỗi thời gian đơn biến (univariate time series) và chuỗi thời gian đa biến (multivariate time series).
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 [15]. Chuỗi con Cho một chuỗi thời gian T có chiều dài n, một chuỗi con C của T là một dãy có chiều dài m (với ) có vị trí liền nhau trong chuỗi thời gian T. Một chuỗi con C của T cũng có thể được xem là một chuỗi thời gian với chiều dài m.
16 Một điều cần lưu ý, là khái niệm “chuỗi con” khác với khái niệm “chuỗi tuần tự”. Nếu khái niệm “chuỗi tuần tự” cho phép các phần tử của chuỗi có thể không liên tục so với chuỗi ban đầu, thì khái niệm “chuỗi con C” của một chuỗi thời gian T chỉ chấp nhận những phần tử liên tiếp nhau trong chuỗi thời gian T. Bên dưới là một ví dụ về chuỗi con của một chuỗi thời gian. Cho chuỗi thời gian T = (3, 5, 1, 12, 4, 7).
Khi đó, C1 = (12, 4, 7) được gọi là một chuỗi con của chuỗi thời gian T. Tuy nhiên, C2 = (3, 1,12, 4) không được xem là một chuỗi con của chuỗi thời gian T, vì “3” và “1” là các giá trị không liên tiếp nhau trong T. Các công trình nghiên cứu thường áp dụng phương pháp cửa sổ trượt (windows sliding) để lấy các chuỗi con trong một chuỗi thời gian để phục vụ cho bài toán nghiên cứu. Số lượng của các chuỗi con lấy được là bằng nhau và bằng độ dài của cửa sổ trượt.2 Ví dụ về chuỗi con C của chuỗi thời gian T [16] 2.
Trùng khớp Cho một số thực dương R (do người dùng định nghĩa) và một chuỗi thời gian T. Biết rằng T chứa một chuỗi con C bắt đầ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, tức D(C, M) < R, thì M là một chuỗi con trùng khớp với C và ngược lại. Một số bài toán khai phá mẫu phổ biến trong cơ sở dữ liệu chuỗi thời gian 2. Bài toán khai phá mẫu phổ biến Khai phá mẫu phổ biến trong cơ sở dữ liệu chuỗi thời gian là quá trình khai phá, tìm ra các sự kiện hay các mẫu (pattern) trên các chuỗi thời gian, mà các mẫu này có tần suất xuất hiện thường xuyên trong cơ sở dữ liệu.
Để xác định được một mẫu (pattern) có là mẫu phổ biến hay không, người ta dựa vào một giá trị gọi là giá trị ngưỡng hỗ trợ tối thiểu (minimum support threshold) min_supp. Nếu tuần suất xuất hiện của một mẫu có giá trị lớn hơn hoặc bằng giá trị của ngưỡng hỗ trợ tối thiểu, ta gọi mẫu đó là mẫu phổ biến. Ý nghĩa của bài toán khai phá mẫu phổ biến trong các cơ sở dữ liệu lớn hay trong trong cơ sở dữ liệu chuỗi thời gian đều có tác dụng lớn và được áp dụng phổ biến trong nhiều lãnh vực khác nhau, phục vụ cho nhu cầu dự báo dữ liệu trong tương lai. Ví dụ trong lãnh vực chứng khoán, việc khai phá tìm ra được những mẫu phổ biến về dữ liệu hiện tại, giúp người dùng dự đoán được những diễn biến của dữ liệu chứng khoán trong tương lai.
Bài toán khai phá mẫu phổ biến gia tăng Với khai phá mẫu phổ biến, việc khai phá chỉ thực hiện trên tập dữ liệu hoàn toàn tĩnh, nghĩa là không có thêm bất kì biến động gì nữa về dữ liệu. Tuy nhiên, trong thực tế, cơ sở dữ liệu chuỗi thời gian luôn luôn sẽ có sự gia tăng dữ liệu theo thời gian. Khi đó, các mẫu phổ biến trước đó không còn phù hợp nữa với tình hình dữ liệu hiện tại. Vì vậy, để giải quyết vấn đề này, khái niệm “khai phá mẫu phổ biến gia tăng” xuất hiện và dần trở thành mối quan tâm của nhiều công trình nghiên cứu.
Khai phá mấu phổ biến gia tăng là quá trình khai phá, hay cập nhật lại tập các mẫu phổ biến mỗi khi cơ sở dữ liệu được mở rộng bởi các dữ liệu mới được thêm vào, đảm bảo tập mẫu phổ biến luôn đúng trong bất kì tình trạng nào của cơ sở dữ liệu. Khai phá mẫu tuần tự phổ biến 2. Định nghĩa Khai phá mẫu tuần tự phổ biến 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ở dữ 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”.
Vấn đề khai phá mẫu tuần tự phổ biến được Agrawal và Srikant đề xuất lần đầu năm 1995, 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. Một số khái niệm thường gặp trong khai phá mẫu tuần tự phổ biến - Cho I = {I1, I2,…, Ip} là tập tất cả items. - Tập phần 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 <e1, e2,. , en> sao cho sự kiện e1 xảy ra trước sự kiện e2, e2 xảy ra trước e3,… - 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. Ví dụ: <(AB)C> là một 3 – sequence và có kích thước là 3.
- Chuỗi con: chuỗi β = <b1 b2 … bm> được gọi là chuỗi con của chuỗi α = <a1 a2 … an> hay α là chuỗi cha của β, ký hiệu β ⊆ α, nếu tồn tại những số nguyên 1 ≤ j1 < j2 < … < j2 ≤ m, sao cho b1 ⊆ aj1, b2 ⊆ aj2, …, bm ⊆ ajm. - Độ hỗ trợ (support): Cho cơ sở dữ liệu chuỗi D, mỗi chuỗi có một chỉ số định danh duy nhất. Độ hỗ trợ tuyệt đối của một mẫu tuần tự f là tổng số chuỗi trong 19 D có chứa f. Độ hỗ trợ tương đối của f là tỉ lệ phần trăm chuỗi trong D chứa f.
Ở đây mức hỗ trợ tuyệt đối hoặc tương đối sẽ được sử dụng chuyển đổi qua lại, kí hiệu là sup(f). - Mẫu tuần tự phổ biến: Cho trước ngưỡng hỗ trợ tối thiểu (minSup) xác định bởi người dùng, minSup ∈ (0, 1]. Một mẫu tuần tự f được coi là phổ biến nếu độ hỗ trợ của nó lớn hơn hoặc bằng minSup: sup(f) ≥ minSup, khi đó f được gọi là mẫu tuần tự phổ biến. Một số kỹ thuật khai phá mẫu phổ biến 2.
Giải thuật Apriori Giải thuật Apriori là một trong những giải thuật nền tảng của bài toán khai phá mẫu phổ biến, được đề xuất bởi R. Ý tưởng chính của giải thuật là tiếp cận theo vòng lặp từng mức (level wise), mà k- itemsets sẽ được sử dụng để tìm kiếm (k+1) itemsets. Ở bước đầu tiên, giải thuật sẽ thực hiện duyệt hết toàn bộ cơ sở dữ liệu và đếm số lần xuất hiện của mỗi item trong tập, những item nào có số lần xuất hiện thỏa ngưỡng hỗ trợ tối thiểu min_supp (đã đề cập ở trên, phần giới thiệu bài toán khai phá mẫu phổ biến) sẽ được chọn là các mẫu phổ biến đầu tiên, gọi tập gồm các mẫu phổ biến này là tập 1-itemsets, kí hiểu L1. Sau đó, việc khai phá sẽ được thực hiện tiếp tục trên tập mẫu phổ biến L1 này để tiếp tục tìm tập 2-itemsets, kí hiệu L2.
Cứ thế tiếp tục, tìm tập 3-itemsets,. ,(k-1)-itemset, k-itemset,… cho tới khi không thể tìm thêm được tập k-itemset nào nữa, giải thuật kết thúc.3 Giải thuật Apriori [17] 2. Giải thuật FP-Growth Giải thuật FP-Growth được đề xuất bởi Han và các cộng sự vào năm 2000 cho phép tìm ra tập itemsets phổ biến mà không cần tạo ra tập ứng viên. Hướng tiếp cận chính của giải thuật là áp dụng chiến thuật chia để trị.
Ban đầu, dữ liệu trong cơ sở dữ liệu được biểu diễn lại dưới dạng cấu trúc cây, gọi là FP-Tree (Frequent Pattern Tree). Sau đó giải thuật chia không gian được nén thành một tập các cơ sở dữ liệu điều kiện (conditional database), đây là một dạng CSDL đã được lược bỏ thông tin và đều có liên hệ với một frequent item. Cuối cùng, thực hiện khai phá trên mỗi cơ sở dữ liệu dạng này một cách độc lập. 21 CHƯƠNG 3: CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN Nội dung của chương này, trình bày các công trình nghiên cứu liên quan đến nội dung mà đề tài đang quan tâm nghiên cứu, bao gồm các kỹ thuật về khai phá mẫu phổ biến, khai phá mẫu phổ biến gia tăng, v.
Tuy nhiên, từ một tập dữ liệu thô ban đầu cho đến khi thu nhận được tập kết quả khai phá cuối cùng, phải đi qua một quá trình gồm nhiều giai đoạn tuần tự liên quan đến nhau. Do đó, nội dung được trình bày trong chương 3 này cũng bao gồm một số công trình nghiên cứu có liên quan đến các giai đoạn thực hiện việc khai phá mẫu.