Luận văn thạc sĩ khoa học máy tính khai phá gia tăng mẫu phổ biến trong cơ sở dữ liệu chuỗi thời gian

Luận văn thạc sĩ khoa học máy tính tập trung khai phá gia tăng mẫu phổ biến trong cơ sở dữ liệu chuỗi thời gian, ứng dụng hiệu quả trong phân tích dữ liệu.

• Tác giả: Trần Ngọc Như Quỳnh
• Người hướng dẫn: TS. Võ Thị Ngọc Châu
• Trường học: Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khai phá gia tăng mẫu phổ biến trong cơ sở dữ liệu chuỗi thời gian
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu đề tài

Luận văn thạc sĩ này tập trung vào khai phá dữ liệu trong cơ sở dữ liệu chuỗi thời gian, đặc biệt là mẫu phổ biến gia tăng. Chuỗi thời gian là chuỗi các giá trị đo lường tại các thời điểm cách đều nhau, được ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, y tế, và môi trường. Với sự gia tăng dữ liệu theo thời gian, việc khai phá mẫu phổ biến trở nên phức tạp và cần thiết. Mục tiêu của đề tài là đề xuất phương pháp khai phá gia tăng mẫu phổ biến trong cơ sở dữ liệu chuỗi thời gian, cải tiến từ công trình nghiên cứu năm 2008. Ý nghĩa của đề tài nằm ở việc nâng cao hiệu suất khai phá dữ liệu, đặc biệt trong bối cảnh dữ liệu liên tục được cập nhật.

1.1. Vấn đề nghiên cứu

Dữ liệu chuỗi thời gian ngày càng phổ biến và quan trọng trong các ứng dụng thực tế. Tuy nhiên, việc dữ liệu gia tăng theo thời gian đặt ra thách thức lớn trong khai phá dữ liệu. Bài toán khai phá mẫu phổ biến gia tăng nhằm giải quyết vấn đề này bằng cách cập nhật các mẫu phổ biến khi dữ liệu mới được thêm vào. Đề tài tập trung vào việc cải tiến các kỹ thuật khai thác dữ liệu hiện có để tối ưu hóa quá trình này.

1.2. Mục tiêu và ý nghĩa

Mục tiêu chính của đề tài là phát triển phương pháp khai phá mẫu phổ biến gia tăng trong cơ sở dữ liệu chuỗi thời gian, đảm bảo hiệu suất cao cả về thời gian và không gian lưu trữ. Ý nghĩa khoa học của đề tài nằm ở việc đóng góp vào lĩnh vực còn ít được nghiên cứu này, trong khi ý nghĩa thực tiễn là cung cấp giải pháp hiệu quả cho các bài toán dự báo và phân tích dữ liệu trong thực tế.

II. Cơ sở lý thuyết

Chương này trình bày các khái niệm cơ bản về dữ liệu chuỗi thời gian, mẫu phổ biến, và khai phá dữ liệu. Chuỗi thời gian được định nghĩa là chuỗi các giá trị đo lường tại các thời điểm cách đều nhau, có thể là chuỗi đơn biến hoặc chuỗi đa biến. Mẫu phổ biến là các sự kiện hoặc chuỗi xuất hiện thường xuyên trong dữ liệu, được xác định dựa trên ngưỡng hỗ trợ tối thiểu. Khai phá mẫu phổ biến gia tăng là quá trình cập nhật các mẫu phổ biến khi dữ liệu mới được thêm vào, đảm bảo tính chính xác và kịp thời của kết quả.

2.1. Dữ liệu chuỗi thời gian

Chuỗi thời gian là chuỗi các giá trị đo lường tại các thời điểm cách đều nhau, được ứng dụng rộng rãi trong nhiều lĩnh vực. Chuỗi đơn biến chỉ chứa một quan sát tại mỗi thời điểm, trong khi chuỗi đa biến chứa nhiều quan sát. Chuỗi con là một dãy liên tiếp các giá trị trong chuỗi thời gian, được sử dụng trong các bài toán khai phá dữ liệu.

2.2. Khai phá mẫu phổ biến

Khai phá mẫu phổ biến là quá trình tìm ra các sự kiện hoặc chuỗi xuất hiện thường xuyên trong dữ liệu, dựa trên ngưỡng hỗ trợ tối thiểu. Khai phá mẫu phổ biến gia tăng là quá trình cập nhật các mẫu phổ biến khi dữ liệu mới được thêm vào, đảm bảo tính chính xác của kết quả. Các kỹ thuật khai thác dữ liệu như Apriori và FP-Growth thường được sử dụng trong quá trình này.

III. Các công trình nghiên cứu liên quan

Chương này tổng hợp các công trình nghiên cứu liên quan đến khai phá mẫu phổ biến và khai phá dữ liệu chuỗi thời gian. Các kỹ thuật thu giảm số chiều như PAA, PLA, và PCA được sử dụng để xử lý dữ liệu chuỗi thời gian. Các kỹ thuật rời rạc hóa như SAX và ESAX giúp chuyển đổi dữ liệu liên tục thành dữ liệu rời rạc. Các giải thuật khai phá mẫu tuần tự như GSP, SPADE, và PrefixSpan được sử dụng để tìm các mẫu tuần tự phổ biến. Các giải thuật khai phá gia tăng như ISM, IncSpan, và IncSP được đề xuất để cập nhật các mẫu phổ biến khi dữ liệu mới được thêm vào.

3.1. Kỹ thuật thu giảm số chiều

Các kỹ thuật thu giảm số chiều như PAA, PLA, và PCA được sử dụng để giảm kích thước dữ liệu chuỗi thời gian, giúp tối ưu hóa quá trình khai phá dữ liệu. PAA chia chuỗi thời gian thành các đoạn nhỏ và tính giá trị trung bình của mỗi đoạn. PLA sử dụng các đoạn thẳng để xấp xỉ chuỗi thời gian. PCA giảm số chiều dữ liệu bằng cách tìm các thành phần chính.

3.2. Kỹ thuật rời rạc hóa

Các kỹ thuật rời rạc hóa như SAX và ESAX chuyển đổi dữ liệu liên tục thành dữ liệu rời rạc, giúp đơn giản hóa quá trình khai phá dữ liệu. SAX chia chuỗi thời gian thành các đoạn và gán mỗi đoạn một ký hiệu. ESAX là phiên bản mở rộng của SAX, cho phép xử lý dữ liệu đa biến.

IV. Hướng tiếp cận giải quyết vấn đề

Chương này trình bày hướng tiếp cận của đề tài trong việc giải quyết bài toán khai phá mẫu phổ biến gia tăng trong cơ sở dữ liệu chuỗi thời gian. Đề tài tập trung vào việc cải tiến giải thuật Optimizied-Join từ công trình nghiên cứu năm 2008, đồng thời đề xuất giải pháp gia tăng theo chiều dọc cho cơ sở dữ liệu chuỗi thời gian. Môi trường giả lập được thiết lập để kiểm tra hiệu quả của các giải thuật trong các trường hợp gia tăng dữ liệu khác nhau.

4.1. Cải tiến giải thuật Optimizied Join

Đề tài cải tiến giải thuật Optimizied-Join bằng cách điều chỉnh một số bước trong quá trình thực hiện, đồng thời bổ sung giải pháp gia tăng theo chiều dọc cho cơ sở dữ liệu chuỗi thời gian. Giải thuật cải tiến được thiết kế để xử lý hiệu quả các trường hợp gia tăng dữ liệu, đảm bảo tính chính xác và kịp thời của kết quả.

4.2. Môi trường giả lập

Môi trường giả lập được thiết lập để kiểm tra hiệu quả của các giải thuật trong các trường hợp gia tăng dữ liệu khác nhau. Các bộ dữ liệu thực nghiệm được sử dụng để đánh giá hiệu suất của giải thuật cải tiến so với các giải thuật truyền thống như Brute-Force.

V. Thực nghiệm

Chương này trình bày quá trình thực nghiệm với các bộ dữ liệu khác nhau để đánh giá hiệu quả của giải thuật cải tiến. Các bộ dữ liệu bao gồm dữ liệu về số ca sinh nở ở California, số liệu về vết đen mặt trời, và một bộ dữ liệu mô phỏng. Kết quả thực nghiệm cho thấy giải thuật cải tiến có hiệu suất cao hơn so với giải thuật Brute-Force trong cả hai trường hợp gia tăng dữ liệu theo chiều ngang và chiều dọc.

5.1. Tiền xử lý dữ liệu

Các bộ dữ liệu thực nghiệm được tiền xử lý để chuẩn bị cho quá trình khai phá dữ liệu. Các bước tiền xử lý bao gồm làm sạch dữ liệu, chuẩn hóa dữ liệu, và chia dữ liệu thành các chuỗi con để phục vụ cho bài toán khai phá mẫu phổ biến.

5.2. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy giải thuật cải tiến có hiệu suất cao hơn so với giải thuật Brute-Force trong cả hai trường hợp gia tăng dữ liệu theo chiều ngang và chiều dọc. Giải thuật cải tiến cũng cho thấy khả năng xử lý hiệu quả các bộ dữ liệu lớn, đáp ứng nhu cầu thực tế.

VI. Kết luận

Luận văn thạc sĩ này đã đề xuất phương pháp khai phá mẫu phổ biến gia tăng trong cơ sở dữ liệu chuỗi thời gian, cải tiến từ công trình nghiên cứu năm 2008. Kết quả thực nghiệm cho thấy giải thuật cải tiến có hiệu suất cao hơn so với các giải thuật truyền thống. Hướng phát triển trong tương lai bao gồm việc áp dụng các kỹ thuật học máy để nâng cao hiệu quả của quá trình khai phá dữ liệu, cũng như mở rộng ứng dụng của phương pháp trong các lĩnh vực khác nhau.

6.1. Đóng góp của luận văn

Luận văn đã đóng góp vào lĩnh vực khai phá mẫu phổ biến gia tăng trong cơ sở dữ liệu chuỗi thời gian, cung cấp giải pháp hiệu quả cho các bài toán dự báo và phân tích dữ liệu trong thực tế. Giải thuật cải tiến được đề xuất đã chứng minh hiệu suất cao trong các thực nghiệm với các bộ dữ liệu khác nhau.

6.2. Hướng phát triển

Hướng phát triển trong tương lai bao gồm việc áp dụng các kỹ thuật học máy để nâng cao hiệu quả của quá trình khai phá dữ liệu, cũng như mở rộng ứng dụng của phương pháp trong các lĩnh vực khác nhau. Ngoài ra, việc tối ưu hóa giải thuật cải tiến để xử lý các bộ dữ liệu lớn hơn cũng là một hướng nghiên cứu tiềm năng.

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

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.