Chương 1: GIỚI THIỆU ĐỀ TÀI 1.1 Dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian là một chuỗi các giá trị hay sự kiện có được bằng cách lặp lại một phép đo theo thời gian. Các giá trị thường đo theo thời khoảng (mili giây, giây, phút, giờ, ngày, tuần, tháng, năm). Dữ liệu chuỗi thời gian phổ biến trong nhiều ứng dụng như phân tích thị trường chứng khoán, phân tích ngân sách, các hiện tượng tự nhiên (nhiệt độ, gió, khí hậu, động đất, .), chữa bệnh,… Dữ liệu chuỗi thời gian thường có kích thước rất lớn, có thể lên đến nhiều gigabyte trong vòng một ngày (như dữ liệu chứng khoán), thậm chí trong vòng một phút (dữ liệu từ không gian NASA). Như vậy, bằng cách nào chúng ta có thể tìm được mối liên hệ trong dữ liệu chuỗi thời gian, bằng cách nào chúng ta có thể phân tích một lượng dữ liệu lớn như vậy để có thể tìm ra các mẫu tương tự hay thường xuyên, các xu hướng, bất thường một cách hiệu quả? Điều này trở thành một vấn đề quan trọng và đầy thử thách cho các nhà phân tích dữ liệu.1: Biểu diễn một loại dữ liệu chuỗi thời gian [37] 1.2 Khai phá luật trên dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian xuất hiện một cách tự nhiên trong hầu hết các lĩnh vực tự nhiên, xã hội cũng như nhiều ngành khác.
Khối dữ liệu này chứa nhiều thông tin hữu ích cho các nhà nghiên cứu của từng lĩnh vực tương ứng. Trong nghiên cứu khí tượng, dữ liệu chuỗi thời gian có thể được khai thác để dự báo khí hậu. Trong kinh tế, các nhà kinh tế muốn xác định xu hướng thay đổi trong thu nhập gia đình theo thời gian; các nhà đầu tư muốn dự đoán giá của một loại cổ phiếu nào đó sẽ thay đổi như thế nào theo thời gian… Từ đây ta thấy rằng việc phân tích dữ liệu chuỗi thời gian để khám phá các luật biến đổi trong dữ liệu chuỗi thời gian có ý nghĩa rất quan trọng trong nhiều lĩnh vực của đời sống. Khai phá luật trên dữ liệu chuỗi thời gian là một công việc quan trọng trong khai phá dữ liệu chuỗi thời gian vì đầu ra của nó thường nhắm vào con người, cung cấp cho người dùng một cái nhìn sâu sắc hơn về dữ liệu.
10 Khai phá luật trên chuỗi thời gian dựa trên tỉ số thay đổi và giải thuật FP-Growth Khai phá luật là một công việc điển hình trong khai phá dữ liệu. Khai phá luật kết hợp (Agrawal và các cộng sự [3]) là một trong những thuật toán nổi tiếng nhất. Tuy nhiên, nó chỉ tập trung vào các ký hiệu tượng trưng (symbolic) trong các phiên làm việc. Vì thế, nhiều nhà nghiên cứu đã đề xuất ra nhiều thuật toán mới hoặc được cải tiến nhằm khai phá luật trong dữ liệu chuỗi thời gian.
Hướng tiếp cận thông thường là đầu tiên sẽ rời rạc hóa dữ liệu chuỗi thời gian thành những đoạn và chuyển những đoạn này thành ký tự. Sau đó, các luật có thể được khai phá trong miền ký tự vừa được chuyển đổi. Das và các cộng sự [9] gom cụm các chuỗi con để tìm ra các ký tự, và sau đó áp dụng một thuật toán khai phá luật đơn giản để tìm ra luật. Last và các cộng sự [23] tập trung vào việc khám phá các luật kết hợp mờ, nó dựa vào nguyên lý tính toán tri thức (perception) và các kỹ thuật xử lý tín hiệu.
Leigh và các cộng sự [30] phát triển phương pháp khám phá luật thuộc về lĩnh vực tài chính, sử dụng kỹ thuật “bull flag”. Nhóm nghiên cứu của Hoppner [13] đã quan tâm tới thời khoảng và phát triển một framework để khám phá ra các luật thời gian, các luật này được hình thành từ một tập các mẫu thường xuyên trong một chuỗi trạng thái. Framework biểu diễn các đoạn của chuỗi thời gian bằng các thuộc tính (tăng, giá trị cao, cực trị cao) và khám phá ra các mối quan hệ thời khoảng được mô tả theo mẫu của logic thời khoảng. Một nhóm nghiên cứu khác của Hetland và Seatrom [24] đưa ra một phương pháp khai phá luật dựa trên lập trình di truyền và phần cứng chuyên dụng.
Họ cũng kiểm tra vai trò của rời rạc hóa khi rút ra các luật tiên đoán trên chuỗi thời gian. Cotofrei và Stoffel [25] đề xuất một phương pháp dựa trên logic vị từ cho việc khai phá luật. Theo hướng tiếp cận này, đầu tiên sẽ biến đổi chuỗi dữ liệu ban đầu thành chuỗi các sự kiện, sau đó rút ra các luật thời gian bằng cách sử dụng cây phân lớp.3 Mục tiêu đề tài Mục tiêu của đề tài là phát triển một giải thuật khai phá luật trên dữ liệu chuỗi thời gian nhằm khám phá ra đúng được các mẫu thức thời gian thường xuyên và luật từ dữ liệu chuỗi thời gian và có ý nghĩa hơn với người sử dụng. Các dạng mẫu thức thời gian và luật này vẫn chưa được đầu tư nhiều trong các công trình hiện tại về bài toán khai phá luật trên dữ liệu chuỗi thời gian.
Hiệu suất của giải thuật cũng được quan tâm để nâng cao hiệu quả của quá trình khai phá luật. Đề tài sẽ cải tiến giải thuật FP-Growth để nâng cao hiệu quả của quá trình khai phá ra các mẫu thường xuyên, từ đó cải thiện quá trình khai phá luật, áp dụng quan hệ thời gian Allen vào quá trình khai phá luật làm cho các luật được sinh ra sẽ dễ hiểu hơn và gần gũi hơn với người dùng.4 Phạm vi đề tài Đề tài hiện thực quá trình khai phá luật theo dạng: VT →t VP(s, c) (1) Ở đây, VT chỉ phần đầu của luật, VP là kết quả của luật và quan hệ thời gian t ở đây dựa trên các phép toán quan hệ thời gian của Allen; s,c là độ hỗ trợ và độ tin cậy tương ứng của luật. 11 Khai phá luật trên chuỗi thời gian dựa trên tỉ số thay đổi và giải thuật FP-Growth Trong giới hạn thời gian được phép, đề tài chỉ tập trung khai phá luật theo dạng luật (1) trên chuỗi thời gian và đánh giá kết quả đạt được. Vì dữ liệu chuẩn cho bài toán khai phá luật trên chuỗi thời gian chưa phổ biến nên luận văn sử dụng dữ liệu chứng khoán của thị trường chứng khoán Việt Nam làm dữ liệu thực nghiệm.5 Ý nghĩa của đề tài 1.
Ý nghĩa khoa học: - Giải thuật khai phá luật trên dữ liệu chuỗi thời gian mới được định nghĩa dựa trên sự cải tiến của giải thuật FP-growth. Giải thuật được kiểm chứng là khai phá ra đúng được các mẫu thức thường xuyên và luật; đồng thời hiệu quả hơn giải thuật brute-force. - Đề tài hiện thực một quá trình khai phá luật trên dữ liệu chuỗi thời gian. Luật được khai phá có quan tâm nhiều đến yếu tố thời gian làm cho các luật được khai phá ra dễ hiểu hơn do đó có ý nghĩa hơn với người dùng.
Ý nghĩa thực tiễn: - Kết quả của quá trình khai phá có thể áp dụng trên nhiều miền dữ liệu khác nhằm khai phá ra các thông tin có ý nghĩa trên nhiều miền dữ liệu khác nhau. Kết quả này có thể áp dụng vào các hệ thống dự đoán giá trị tương lai cho các loại dữ liệu chuỗi thời gian như: trong chứng khoán có thể dự đoán giá cổ phiếu của một loại cổ phiếu nào đó biến đổi như thế nào (tăng, giảm, ổn định) trong tương lai hoặc dự đoán sau khoảng thời gian t bao lâu thì giá của một cổ phiếu nào đó là tăng, giảm hay ổn định, kết quả này giúp cho các nhà đầu tư có thêm cơ sở để đưa ra quyết định đầu tư vào loại cổ phiếu nào là có lợi cho họ. Kết quả này cũng có thể áp dụng cho các miền dữ liệu chuỗi thời gian khác như với dữ liệu về thời tiết, kết quả khai phá giúp các nhà dự báo thời tiết có thể dự đoán thời tiết sẽ biến động như thế nào trong tương lai hoặc là ứng với thời tiết hiện như vậy thì sau bao lâu sẽ xảy ra bão, hạn hán, động đất,… 12 Khai phá luật trên chuỗi thời gian dựa trên tỉ số thay đổi và giải thuật FP-Growth Chương 2: TỔNG QUAN VỀ CÁC CÔNG TRÌNH LIÊN QUAN Kết quả của việc phát triển các kỹ thuật tự động thu thập và lưu trữ dữ liệu lớn là chúng ta đang sống trong thời đại bùng nổ dữ liệu. Có rất nhiều ứng dụng tạo ra một lượng lớn dữ liệu chuỗi thời gian như dữ liệu về chứng khoán, dữ liệu điện tâm đồ, các hiện tượng tự nhiên, ….
Việc khai phá luật trên các tập dữ liệu này tạo ra một thách thức lớn cho các nhà phân tích dữ liệu. Người ta thường quan tâm đến việc phân tích dữ liệu chuỗi thời gian vì hai lý do: - Mô hình chuỗi thời gian: để có được cái nhìn sâu hơn vào cơ chế tạo ra chuỗi thời gian. - Dự đoán chuỗi thời gian: để dự đoán giá trị tương lai của biến chuỗi thời gian. Theo truyền thống, người ta xây dựng các mô hình cho dữ liệu chuỗi thời gian và sau đó đưa các giá trị quan sát thực tế vào những mô hình này.
Nếu một mô hình thành công trong việc giải thích chuỗi thời gian quan sát được thì giá trị tương lai của chuỗi thời gian có thể được tiên đoán. Khai phá luật trên dữ liệu chuỗi thời gian là tìm ra các quy luật thể hiện mối liên hệ kết hợp, tương quan giữa các mẫu thức trên tập chuỗi thời gian. Phần này sẽ trình bày về quá trình khai phá luật và các công trình liên quan của quá trình này.1 Tiền xử lý Dữ liệu chuỗi thời gian thường được thu thập từ nhiều nguồn khác nhau, dữ liệu thu được thường là dữ liệu thô và có thể không nhất quán do nhiều nguyên nhân như thiết bị đo thiếu chính xác, ảnh hưởng của các yếu tố tự nhiên,… Khi đó, nếu thực hiện phân tích trên tập dữ liệu này sẽ cho ra những kết quả thiếu chính xác, và không có ý nghĩa, do vậy, trước khi đưa dữ liệu này vào phân tích cần phải thực hiện một số thao tác tiền xử lý để chuẩn hóa dữ liệu này trước. Tiền xử lý dữ liệu chuỗi thời gian đòi hỏi phải có các phương pháp đặc biệt để kết hợp với chiều thời gian.
Một bước quan trọng trong quá trình này là giảm nhiễu, việc lọc nhiễu có thể thực hiện bằng cách dùng các bộ lọc kỹ thuật số [27] hoặc wavelet thresholding. Các kỹ thuật tách giá trị đặc trưng được dùng để chuyển chuỗi giá trị gốc sang nhiều miền giá trị có ý nghĩa khác hoặc là để cung cấp thêm thông tin.
