CHƯƠNG 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI Chương này giới thiệu sơ lược về đề tài, mục tiêu và phạm vi nghiên cứu cũng như cấu trúc của đề tài. CƠ SỞ LÝ THUYẾT Chương này trình bày chi tiết về các vấn đề lý thuyết sẽ được áp dụng trong đề tài như: dữ liệu chuỗi thời gian, cây hậu tố, mảng hậu tố, mảng hậu tố nâng cao, mã hóa dữ liệu chuỗi thời gian thành chuỗi xu hướng. NHỮNG CÔNG TRÌNH LIÊN QUAN Chương này trình bày một số công trình nghiên cứu liên quan đến đề tài như công trình phát hiện tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian, công trình phát hiện motif trên dữ liệu chuỗi thời gian dựa vào xác xuất, và công trình về truy vấn hình dạng dữ liệu chuỗi thời gian.
PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ Chương này trình bày về việc sử dụng mảng hậu tố nâng cao, cây hậu tố cùng với phương pháp xấp xỉ tuyến tính từng đoạn để phát hiện tất cả các mẫu xu hướng thường xuyên và phương pháp xấp xỉ gộp từng đoạn để phát hiện tất cả các motif trong dữ liệu chuỗi thời gian CHƯƠNG 5. THỰC NGHIỆM VÀ ĐÁNH GIÁ Trang 4 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Chương này trình bày thực nghiệm, đánh giá độ chính xác và thời gian thực hiện để phát hiện tất cả các mẫu xu hướng và phát hiện tất cả các motif bằng mảng hậu tố nâng cao và cây hậu tố trong dữ liệu chuỗi thời gian. KẾT LUẬN Chương này đánh giá kết quả đạt được, các mặt hạn chế và hướng phát triển của đề tài. Trang 5 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc CHƯƠNG 2.
CƠ SỞ LÝ THUYẾT Chương này sẽ trình bày về các công trình liên quan đến bài toán tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian, các công trình về cây hậu tố, mảng hậu tố, mảng hậu tố nâng cao, phương pháp thu giảm số chiều, phương pháp rời rạc hóa dữ liệu.1 DỮ LIỆU CHUỖI THỜI GIAN Một chuỗi thời gian (Time Series) chiều dài 𝑚 là một tập hợp có thứ tự gồm 𝑚 giá trị thực. Ta ký hiệu chuỗi thời gian là 𝑇 = 𝑥1 , 𝑥2 , … , 𝑥𝑚 với 𝑥𝑖 là các số thực, 𝑚 là một số nguyên. Việc xác định các xu hướng thường xuyên của một chuỗi thời rất quan trọng trong bài toán dự báo chuỗi thời gian. Nó giúp ta lựa chọn được mô hình dự báo phù hợp hay giúp cải tiến mô hình đã có chính xác hơn.
Và các mẫu quan sát được theo thời gian dựa trên các chuỗi thời gian chính là cơ sở để hiểu được đặc tính cũng như là dự báo các hành vi tương lai của đối tượng đó. Chuỗi con (𝑠𝑢𝑏𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒) 𝐶 có chiều dài 𝑛 của một chuỗi thời gian 𝑇 có chiều dài 𝑚 (𝑚 ≤ 𝑛) là một đoạn các giá trị liên tục nằm trong T. Ta ký hiệu 𝐶 = 𝑥 𝑝 , 𝑥𝑝+1 , … , 𝑥𝑝+𝑛−1 , với 1 ≤ 𝑝 ≤ 𝑚 − 𝑛 + 1.2 CÂY HẬU TỐ Cho ∑ là một tập hữu hạn các phần tử, với mỗi phần tử là một ký tự trong tập ký tự (𝑎𝑙𝑝ℎ𝑎𝑏𝑒𝑡), các phần tử thuộc ∑ gọi là ký tự. ∑* là một tập hợp con của ∑ mà không chứa chuỗi rỗng (∈).
Ta có: ∑∗ = ∑ − {∈} Chiều dài của một chuỗi 𝑥 ký hiệu là |𝑥 |, là số ký tự trong chuỗi 𝑥. Các ký trong chuỗi 𝑥 được đánh số từ 0 đến|𝑥| – 1:=𝑥 = 𝑥0 𝑥1 𝑥2 … 𝑥|𝑥|−1 Trang 6 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Gọi chuỗi 𝑤 là tiền tố của chuỗi 𝑥, ký hiệu 𝑤 ⊏ 𝑥, nếu tồn tại chuỗi 𝑎 để 𝑥 = 𝑤𝑎, chuỗi 𝑤 là hậu tố của chuỗi 𝑥, ký hiệu 𝑤 ⊐ 𝑥, nếu tồn tại chuỗi 𝑎 để 𝑥 = 𝑎𝑤. Một chuỗi vừa có thể là tiền tố vừa là hậu tố của một chuỗi khác. Ví dụ chuỗi XYX vừa là tiền tố vừa là hậu tố của chuỗi XYXYX.
Chuỗi rỗng (∈) vừa là tiền tố vừa là hậu tố của tất cả các chuỗi. Trie hậu tố Cho 𝑆 là một tập hợp gồm 𝑛 chuỗi, các chuỗi này không là tiền tố của nhau. Trie là một cấu trúc dữ liệu dạng cây (hình 2-1) biểu diễn các chuỗi của 𝑆. Trie có các tính chất sau: Mỗi cạnh của Trie có nhãn là một ký tự.
Các cạnh đi từ một nút xuống các nút con có nhãn khác nhau. Mỗi nút trên Trie cũng có một nhãn, ký hiệu 𝑣̅ là chuỗi tạo thành bằng cách nối các ký tự nhãn của cạnh trên đường đi trừ nút gốc xuống nút con. Chiều dài của chuỗi 𝑣̅ được gọi là độ sâu của nút, ký hiệu: 𝑑𝑒𝑝𝑡ℎ(𝑣). Hai nút khác nhau có nhãn khác nhau Ví dụ Trie hậu tố: 𝑆 = {𝐵𝐸𝐴𝑅, 𝐵𝐸𝐿𝐿, 𝐵𝐼𝐷, 𝐵𝑈𝐿𝐿, 𝐵𝑈𝑌, 𝑆𝐸𝐿𝐿, 𝑆𝑇𝑂𝐶𝐾, 𝑆𝑇𝑂𝑃}.
Trie hậu tố Trang 7 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Các chuỗi trong tập 𝑆 phải thỏa mãn tính chất phi tiền tố (prefix-free): tức là không có chuỗi nào là tiền tố của một chuỗi khác trong 𝑆. Không thể xây dựng được cây không thỏa mãn tính chất trên. Ví du: 𝑆 = {ABC, AB}, ta không thể xây dựng được trie hậu tố vì từ nút góc đến các nút lá của Trie ta lần lượt đi qua các nút có nhãn A, AB, ABC. Vì AB ∈ 𝑆 nên ta phải có nút lá của Trie mang nhãn AB, mà ta đã có nhánh của Trie có nhãn AB, nên không thể xây dựng được nút lá có nhãn AB (hình 2.
Không thể xây dựng được Trie với nút lá có nhãn AB Tính chất phi tiền tố là một tính chất quan trọng của cây Trie. Để đảm bảo ta luôn có thể xây dựng được cây Trie, ta dùng một kỹ thuật là bổ sung vào mỗi chuỗi của 𝑆 một ký tự $ ở cuối mỗi chuỗi (hình 2-3) Cho 𝑆 là một tập chứa các hậu tố của 1 chuỗi 𝑇 (𝑇 ∈ ∑∗ ) được gọi là Trie hậu tố của T (hình 2-4). Để thỏa mãn tính chất phi tiền tố, ta thêm vào cuối mỗi phần tử của S ký tự $. Ví dụ: 𝑇 = BANANA$, ta có tập S gồm 7 chuỗi: 𝑆 = {BANANA$, ANANA$, NANA$, ANA$, NA$, A$, $} Trang 8 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Hình 2-3.
Thêm ký tự $ ở cuối mỗi chuỗi Hình 2-4. Trie hậu tố 𝑻 = 𝑩𝑨𝑵𝑨𝑵𝑨$ Cây hậu tố (suffix tree) là một cấu trúc dữ liệu biểu diễn các hậu tố của một chuỗi khác rỗng tương tự như Trie. Cây hậu tố được tạo thành từ Trie hậu tố bằng cách Trang 9 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc ghép các nút con đơn nhánh lại với nhau. Cây hậu tố cho chuỗi 𝑆 có chiều dài 𝑚 có các tính chất sau: Mỗi cạnh của cây có nhãn là một chuỗi thuộc ∑∗.
Các cạnh đi từ một nút xuống các nút con của nó phải có nhãn là các chuỗi có ký tự đầu tiên khác nhau. Mỗi nút 𝑣 trên cây cũng mang một nhãn, nhãn của nút 𝑣, ký hiệu 𝑣̅ là một chuỗi tạo thành bằng các nối tiếp các nhãn cạnh trên đường đi xuống nút 𝑣. Chiều dài của chuỗi 𝑣̅ : 𝑣̅ được gọi là độ sâu của nút 𝑣, ký hiệu: 𝑑𝑒𝑝𝑡ℎ(𝑣). Ngoại trừ nút góc, các nút phải có nhiều hơn một con.
Với mỗi cạnh được gán nhãn bằng một chuỗi con khác rỗng của 𝑆. Mỗi chuỗi con 𝑎 của chuỗi 𝑆 xuất hiện trên một lối đi duy nhất nào đó từ nút gốc. Ví dụ cây hậu tố: 𝑆 = xabxa$ Hình 2-5. Cây hậu tố cho chuỗi xabxa$ 2.3 MẢNG HẬU TỐ Cho một chuỗi 𝑆 = 𝑥1 , 𝑥2 , 𝑥3 , … 𝑥𝑚 ∈ ∑∗ , có duy nhất 𝑥𝑚 = $.
Mảng hậu tố (suffix array) của 𝑆 ký hiệu SA(T) là thứ tự từ điển của tất cả các hậu tố của 𝑆. Trang 10 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc Mảng hậu tố có thể được biểu diễn theo thứ tự từ điển (hình 2-6). Ví dụ: 𝑆= BANANA$, các hậu tố của 𝑆 và mảng hậu tố của 𝑆 theo thứ tự từ điển. Mảng hậu tố theo thứ tự từ điển Mảng hậu tố được đề xuất bởi Manber và Myer [3] như một sự thay thế cho cây hậu tố trong một số bài toán xử lý chuỗi.
Mảng hậu tố có ưu điểm là có cấu trúc đơn giản và tiết kiệm bộ nhớ trong lúc hiện thực. Manber và Mayer cũng đề xuất thuật toán xây dựng mảng hậu tố trực tiếp mà không phải sử dụng cây hậu tố gọi là thuật toán nhân đôi tiền tố (𝑑𝑜𝑢𝑏𝑙𝑖𝑛𝑔 𝑝𝑟𝑒𝑓𝑖𝑥). Thuật toán có độ phức tạp là Ω(𝑛𝑙𝑜𝑔𝑛) trong trường hợp xấu nhất và 𝑂(𝑛) trong trường hợp trung bình để xử lý chuỗi có độ dài 𝑛. Năm 2003, hai nghiên cứu độc lập của Kärkkäinen [4] và Ko [5] đã tìm ra được hai thuật toán tuyến tính xây dựng mảng hậu tố.
Một điểm đáng chú ý trong các thuật toán của Kärkkäinen [4] là chúng đều dựa trên những nhận định rất tinh tế về tính chất của các hậu tố và mối quan hệ giữa các vị trí trong chuỗi. Trang 11 Tìm tất cả các xu hướng thường xuyên trong dữ liệu chuỗi thời gian | Đỗ Duy Quốc 2.4 MẢNG TIỀN TỐ CHUNG DÀI NHẤT Tiền tố chung dài nhất (longest common prefix) của hai chuỗi (𝑥, 𝑦) là chuỗi 𝑧 sao cho 𝑧 vừa là tiền tố của 𝑥, vừa là tiền tố của 𝑦 và 𝑧 có độ dài lớn nhất. Ví dụ: TIền tố chung của sâu banana và bank là ban. Mảng tiền tố chung dài nhất (LCP) là một mảng có kích thước n (giống như suffix array) sao cho giá trị thứ 𝑖 (𝑙𝑐𝑝[𝑖]) là tiền tố chung dài nhất của hậu tố thứ 𝑖 và 𝑖 + 1 Cho T= t0 t1 …., an-1 là mảng hậu tố của T.
Mảng tiền tố chung dài nhất 𝐿𝐶𝑃(𝑇) là dãy số nguyên ( l0 , l1 ,….