ĐẠI HỌC QUỐC GIA TP. HCM
TRƢỜNG ĐẠI HỌC BÁCH KHOA
--------------------

NGUYỄN TRỌNG NHÂN

KẾT CHUỖI CON TRÊN DỮ LIỆU CHUỖI THỜI GIAN
DỰA VÀO VIỆC TÌM CHUỖI CON CHUNG DÀI NHẤT
CỦA HAI CHUỖI, SỬ DỤNG CÂY HẬU TỐ
Ngành: Khoa Học Máy Tính
Mã số: 60.48.01.01

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 6 năm 2018


CƠNG TRÌNH ĐƢỢC HỒN THÀNH TẠI
TRƢỜNG ĐẠI HỌC BÁCH KHOA – ĐHQG - HCM
Cán bộ hƣớng dẫn khoa học: PGS. TS. Dƣơng Tuấn Anh ...................................
Cán bộ chấm nhận xét 1: .......................................................................................
Cán bộ chấm nhận xét 2: .......................................................................................
Luận văn thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Bách Khoa, ĐHQG Tp.
HCM ngày 18 tháng 6 năm 2018.

Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. Chủ tịch:
2. Thƣ ký:
3. Phản biện 1:
4. Phản biện 2:
5. Ủy viên:

Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trƣởng Khoa quản lý
chuyên ngành sau khi luận văn đã đƣợc sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TRƢỞNG KHOA
KH & KT MÁY TÍNH


ĐẠI HỌC QUỐC GIA TP.HCM
TRƢỜNG ĐẠI HỌC BÁCH KHOA

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: Nguyễn Trọng Nhân ....................... MSHV: 1670229
Ngày, tháng, năm sinh: 16/05/1993 ................................ Nơi sinh: Quảng Ngãi
Chuyên ngành: Khoa Học Máy Tính .............................. Mã số: 60.48.01.01
I.

TÊN ĐỀ TÀI: KẾT CHUỖI CON TRÊN DỮ LIỆU CHUỖI THỜI GIAN DỰA VÀO
VIỆC TÌM CHUỖI CON CHUNG DÀI NHẤT CỦA HAI CHUỖI, SỬ DỤNG CÂY
HẬU TỐ ...........................................................................................................................
..........................................................................................................................................
..........................................................................................................................................

II. NHIỆM VỤ LUẬN VĂN:...............................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................

III. NGÀY GIAO NHIỆM VỤ: 03/07/2017 .........................................................................
IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 18/06/2018 ........................................................
V. CÁN BỘ HƢỚNG DẪN: PGS. TS. Dƣơng Tuấn Anh ..................................................
Tp. HCM, ngày ….. tháng ….. năm 2018
CÁN BỘ HƢỚNG DẪN

(Họ tên và chữ ký)

PGS. TS. Dƣơng Tuấn Anh

TRƢỞNG KHOA KH & KTMT

(Họ tên và chữ ký)


i

LỜI CẢM ƠN
Tơi trân trọng gửi lịng tri ân chân thành đến PGS. TS. Dƣơng Tuấn Anh vì
Thầy đã hƣớng dẫn, động viên tơi trong q trình học và làm việc với thái độ ân
cần, bao dung, tận tụy của một nhà giáo chân chính. Khơng chỉ về mặt kiến thức
chun mơn, mà Thầy cịn gián tiếp truyền đạt cho tơi nhiều bài học bổ ích về
cuộc sống.
Tơi chân thành cảm ơn q Thầy, q Cơ vì đã tận tình truyền đạt cho tơi
nhiều tri thức hay và q. Những tri thức này hữu ích với tơi trong suốt q trình
học tập tại trƣờng cũng nhƣ trong tƣơng lai.
Tơi chân thành tri ân gia đình vì đã động viên và tạo mọi điều kiện tốt nhất
để tơi có thể tiếp tục theo đuổi việc học tập, nghiên cứu. Tôi trân trọng dâng tặng
thành quả của luận văn này đến Cha Mẹ. Nhờ công nuôi nấng, dạy dỗ của Ngƣời
mà con mới đƣợc thừa hƣởng những lợi ích nhƣ ngày hơm nay.

Qua đây, tôi cũng gửi lời cảm ơn chân thành đến các anh, các chị là bạn
hữu, đồng nghiệp vì đã tƣ vấn, và góp ý đến tơi trong q trình thực hiện luận văn.


ii

TÓM TẮT LUẬN VĂN
Dữ liệu chuỗi thời gian tồn tại trong rất nhiều ứng dụng thực tế, từ các lĩnh
vực khoa học kỹ thuật cho đến kinh tế, tài chính và là một chủ đề quan trọng trong
lãnh vực khai phá dữ liệu. Trong đó, so trùng chuỗi con là bài toán rất căn bản
đƣợc quan tâm, nghiên cứu nhiều. Kết chuỗi con là bài toán tổng quát hơn của bài
toán so trùng chuỗi con.
Đa phần các nghiên cứu tiếp cận bài tốn kết chuỗi con có hai hƣớng.
Hƣớng thứ nhất kết chuỗi con bằng cách phân đoạn chuỗi thời gian sau đó dựa vào
các đoạn tìm đƣợc thực hiện thao tác tìm kiếm các chuỗi con tƣơng tự. Hƣớng thứ
hai kết chuỗi con bằng cách chuyển hai chuỗi thời gian thành hai dịng ký tự và
tìm chuỗi con chung dài nhất của hai dòng ký tự. Trong đề tài này, chúng tơi thực
hiện theo hƣớng tìm chuỗi con chung dài nhất của hai chuỗi và đề nghị hƣớng tiếp
cận mới cho bài toán bằng việc sử dụng cây hậu tố (suffix tree).
Về tiền xử lý dữ liệu, luận văn sử dụng giải thuật trung bình zero để chuẩn
hóa dữ liệu. Dựa vào kết quả đạt đƣợc sẽ áp dụng phƣơng pháp xấp xỉ gộp từng
đoạn (PAA) và Phép xấp xỉ gộp ký hiệu hóa (SAX) để chuyển chuỗi dữ liệu số về
dạng các dịng ký tự.
Về bài tốn tìm chuỗi con chung dài nhất, luận văn sử dụng giải thuật cây
hậu tố và mảng hậu tố. Ƣu điểm của hƣớng tiếp cận này thời gian xử lý nhanh và
có độ phức tạp tuyến tính. Kết quả thực nghiệm cho thấy giải thuật này có thể chấp
nhận đƣợc trên các bộ dữ liệu lên đến hàng nghìn điểm với độ chính xác khá cao.
Ngồi ra, sau q trình tìm chuỗi con chung dài nhất, luận văn sử dụng
phƣơng pháp Jocor (Join on Correlation) để tính sự tƣơng quan của chuỗi con vừa
tìm đƣợc để kiểm tra xem chuỗi con chung dài nhất tìm thấy có tƣơng ứng với

chuỗi con tƣơng quan nhất của hai chuỗi thời gian.


iii

ABSTRACT
Time series data exists in a wide range of practical applications, from the
fields of science and technology to economics and finance, and is an important
topic in data mining. In that, the subsequence matching is a very basic problem
that is interested, and being researched a lot. The subsequence join between two
time series is the more general problem of the subsequence matching.
Most of the research approaches to address the subsequence join problem
has two directions. The first approach segmenting the time series and then based
on the extracted segments, it performs the subsequence matching. Second
direction converts the two time series into two strings and then find the longest
common substring of the two strings. In this topic, we follow the latter approach
and propose a new approach to the problem by using the suffix tree.
For data preprocessing, the thesis uses a zero-mean normalization and then
applies PAA and SAX transformations to convert the time series into character
strings.
On the problem of finding the longest common subsequence of the two
strings, the thesis uses either the suffix tree or the suffix array. Advantages of this
approach are fast processing time and linear complexity. Experimental results
show that this algorithm can work on datasets of the lengths up to thousands of
data points with high accuracy.
In addition, after finding the longest common subsequence, the thesis uses
the Join on Correlation (Jocor) method to calculate the Pearson’s correlation
coefficient of the substring found in order to check if the longest common
subsequence corresponds to the most correlated subsequence between the two time
series.



iv

LỜI CAM ĐOAN
Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác
nhƣ đã ghi rõ trong luận văn, các cơng việc trình bày trong luận văn này là do
chính tơi thực hiện và chƣa có phần nội dung nào của luận văn này đƣợc nộp để
lấy một bằng cấp ở trƣờng này hoặc trƣờng khác.

Ngày 18 tháng 06 năm 2018

Nguyễn Trọng Nhân


v

MỤC LỤC
LỜI CẢM ƠN................................................................................................. i
TÓM TẮT LUẬN VĂN................................................................................ ii
ABSTRACT ................................................................................................. iii
LỜI CAM ĐOAN ......................................................................................... iv
MỤC LỤC ..................................................................................................... v
DANH SÁCH HÌNH ẢNH ........................................................................ viii
DANH SÁCH BẢNG ................................................................................... x
CHƢƠNG 1 GIỚI THIỆU TỔNG QUAN ĐỀ TÀI ................................... 1
1.1

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


1.1.1 Dữ liệu chuỗi thời gian .............................................................. 1
1.1.2 Bài toán kết chuỗi con trên chuỗi dữ liệu thời gian ................... 2
1.2

Mục tiêu và nhiệm vụ của đề tài....................................................... 4

1.3

Phƣơng pháp nghiên cứu .................................................................. 4

1.4

Ý nghĩa của luận văn ........................................................................ 4

1.5

Những kết quả đạt đƣợc của luận văn .............................................. 4

1.6

Bố cục luận văn ................................................................................ 5

CHƢƠNG 2 CƠ SỞ LÝ THUYẾT ............................................................ 7
2.1

Độ đo khoảng cách ........................................................................... 7

2.1.1 Độ đo Minkowski ...................................................................... 8
2.1.2 Độ đo xoắn thời gian động ........................................................ 9
2.2


Các công trình về biểu diễn chuỗi thời gian ................................... 10

2.2.1 Phƣơng pháp xấp xỉ gộp từng đoạn (PAA) ............................. 10
2.2.2 Phép xấp xỉ gộp ký hiệu hóa SAX ........................................... 12
2.3

Chuỗi thời gian (Time series) ......................................................... 18

2.4

Chuỗi con (Subsequence) ............................................................... 18

2.5

Lập trình song song trên hệ thống đa nhân (multi-core) ................ 18

2.5.1 Xử lý song song ....................................................................... 18
2.5.2 Parallel Extensions trong .Net Framework .............................. 19
2.6

Kết luận chƣơng ............................................................................. 20


vi
CHƢƠNG 3 CÁC CƠNG TRÌNH LIÊN QUAN ..................................... 21
3.1

Cây hậu tố ....................................................................................... 21


3.1.1 Định nghĩa cây hậu tố .............................................................. 21
3.1.2 Xây dựng cây hậu tố bằng giải thuật đơn giản ........................ 23
3.1.3 Giải thuật Ukkonen. ................................................................. 25
3.1.4 Tìm chuỗi con chung dài nhất bằng cây hậu tố ....................... 42
3.2

Mảng hậu tố: ................................................................................... 45

3.2.1 Định nghĩa về mảng hậu tố: ..................................................... 45
3.2.2 Tìm chuỗi con chung dài nhất bằng mảng hậu tố .................... 46
3.2.3 Xử lý song song trên mảng hậu tố. .......................................... 48
3.3 Các cơng trình liên quan đến kết chuỗi con trên dữ liệu chuỗi thời
gian ................................................................................................... 49
3.3.1 Phƣơng pháp kết dựa trên hệ số độ tƣơng quan (Join on
Correlation) ...................................................................................... 49
3.3.2 Phƣơng pháp kết hai vòng lặp lồng nhau (Nested Loop Join) 50
3.3.3 Phƣơng pháp lập chỉ mục trên dữ liệu chuỗi thời gian
(Indexing) ......................................................................................... 50
3.3.4 Phƣơng pháp dựa vào phân đoạn không đồng nhất (nonuniform segmentation) ..................................................................... 51
3.3.5 Phƣơng pháp dựa trên độ đo xoắn thời gian động (Dynamic
Time Warping - DTW). .................................................................... 53
3.4

Kết luận chƣơng ............................................................................. 53

CHƢƠNG 4 PHƢƠNG PHÁP ĐỀ NGHỊ VÀ KẾT QUẢ THỰC
NGHIỆM .......................................................................................... 54
4.1

Phƣơng pháp đề nghị ...................................................................... 54


4.1.1 Khái quát bài tốn kết chuỗi con ............................................. 54
4.1.2 Mơ hình đề nghị cho bài toán kết chuỗi con chung dài nhất ... 55
4.2

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

4.2.1 Môi trƣờng thực nghiệm .......................................................... 56
4.2.2 Dữ liệu thực nghiệm ................................................................ 56
4.2.3 Giao diện chƣơng trình Demo ................................................. 56
4.2.4 Thực nghiệm về độ tƣơng quan của phƣơng pháp kết chuỗi con
đề xuất .............................................................................................. 58
4.2.4.1 Thực nghiệm với bộ dữ liệu Currency..................................... 59


vii
4.2.4.2 Thực nghiệm với bộ dữ liệu Wafer ......................................... 61
4.2.4.3 Thực nghiệm với bộ dữ liệu ECG5000 ................................... 63
4.2.4.4 Thực nghiệm với bộ dữ liệu LSF5 và LSF6 ............................ 65
4.2.4.5 Thực nghiệm với bộ dữ liệu LightCurve ................................. 67
4.2.4.6 Nhận xét ................................................................................... 68
4.2.5 Thực nghiệm so sánh thời gian thực thi của ba giải thuật cây
hậu tố, mảng hậu tố, xử lý song song trên mảng hậu tố. .................. 69
4.2.5.1 So sánh thời gian thực thi trên tập dữ liệu Currency ............... 70
4.2.5.2 So sánh thời gian thực thi trên tập dữ liệu Wafer .................... 71
4.2.5.3 So sánh thời gian thực thi trên tập dữ liệu ECG5000 .............. 72
4.2.5.4 So sánh thời gian thực thi trên tập dữ liệu LSF5 và LSF6 ...... 74
4.2.5.5 So sánh thời gian thực thi trên tập dữ liệu LightCurve ........... 75
4.2.5.6 Nhận xét ................................................................................... 77
4.2.6 Nhận xét chung ........................................................................ 77

CHƢƠNG 5 TỔNG KẾT ......................................................................... 79
5.1

Tổng kết nội dung của luận văn ..................................................... 79

5.2

Những kết quả đạt đƣợc của đề tài ................................................. 79

5.3

Hƣớng phát triển ............................................................................. 80

TÀI LIỆU THAM KHẢO ........................................................................... 81
BẢNG THUẬT NGỮ ANH – VIỆT VÀ TỪ VIẾT TẮT ........................... A
PHẦN LÝ LỊCH TRÍCH NGANG .............................................................. C


viii

DANH SÁCH HÌNH ẢNH
Hình 1-1. Dữ liệu chuỗi thời gian điện tâm đồ.............................................. 2
Hình 1-2. Hai chuỗi dữ liệu thời gian đã đƣợc kết hợp để hiển thị một số
cặp chuỗi con khớp nhau ............................................................................... 2
Hình 1-3. Hai chuỗi dữ liệu thời gian của tỷ giá hối đoái tiền tệ đƣợc kết
hợp để cho thấy mối tƣơng quan cao trong quá khứ. Trục x hiển thị ngày
làm việc. trục y hiển thị tỷ lệ chuyển đổi của INR và SGD so với USD sau
khi bình thƣờng hố. ...................................................................................... 3
Hình 2-1. Cách ánh xạ cặp điểm của độ đo Euclid và độ đo DTW (nguồn
[17]) ............................................................................................................... 9

Hình 2-2. Phƣơng pháp biểu diễn PAA với n = 128, w=8 ([5]) ................. 11
Hình 2-3. Phƣơng pháp chuẩn hóa trung bình zero [6] ............................... 14
Hình 2-4. Minh họa về rời rạc hóa dữ liệu ([5]) .......................................... 15
Hình 2-5. Minh họa 3 dạng biểu diễn chuỗi thời gian và các hàm tính
khoảng cách tƣơng ứng. A) Chuỗi thời gian ban đầu và hàm tính khoảng
cách Euclid. B) Dạng biểu diễn PAA của chuỗi thời gian và hàm tính
khoảng cách DR. C) Dạng biểu diễn SAX và hàm tính khoảng cách
MINDIST ([5]) ............................................................................................ 17
Hình 2-6. Một minh hoạ về chuỗi con......................................................... 18
Hình 3-1. Cây hậu tố của chuỗi “banana”. .................................................. 22
Hình 3-2. Cây hậu tố của chuỗi “banana$”. ................................................ 22
Hình 3-3. Xây dựng cây cho chuỗi “banana” .............................................. 25
Hình 3-4. Cây hậu tố ngầm của chuỗi “banana”. ........................................ 26
Hình 3-5. Sử dụng liên kết hậu tố. [21] ....................................................... 30
Hình 3-6. Minh họa thủ thuật 1. .................................................................. 31
Hình 3-7. Cây hậu tố của chuỗi “banana” trƣớc và sau khi rút gọn cạnh. .. 32
Hình 3-8. Giai đoạn 1. ................................................................................. 35
Hình 3-9. Giai đoạn 2, bƣớc mở rộng 1. ..................................................... 35
Hình 3-10. Giai đoạn 2, bƣớc mở rộng 2. ................................................... 36
Hình 3-11. Giai đoạn 3, bƣớc mở rộng 1. ................................................... 36
Hình 3-12. Giai đoạn 3, bƣớc mở rộng 2. ................................................... 36
Hình 3-13. Giai đoạn 4, bƣớc mở rộng 1. ................................................... 37
Hình 3-14. Giai đoạn 5, bƣớc mở rộng 1. ................................................... 37
Hình 3-15. Giai đoạn 6, bƣớc mở rộng 1. ................................................... 38
Hình 3-16. Giai đoạn 7, bƣớc mở rộng 1. ................................................... 38
Hình 3-17. Giai đoạn 7, bƣớc mở rộng 2 .................................................... 39
Hình 3-18. Giai đoạn 7, bƣớc mở rộng 3 .................................................... 40


ix

Hình 3-19. Giai đoạn 7, bƣớc mở rộng 4 .................................................... 41
Hình 3-20. Giai đoạn 7, bƣớc mở rộng 5. ................................................... 42
Hình 3-21. Cây hậu tố cho chuỗi “xabxa#babxba$”. .................................. 42
Hình 3-22. Cây hậu tố mới sau khi loại bỏ những chuỗi con khơng mong
muốn. ........................................................................................................... 43
Hình 3-23. Cây hậu tố sau khi đƣợc đánh dấu các giá trị “XY”, “X”, “Y” 44
Hình 3-24. Các chuỗi hậu tố của hai chuỗi “ABC” và “BCD” sau khi đƣợc
sắp xếp thứ tự theo bảng chữ cái. ................................................................ 46
Hình 3-25. Giải thuật tìm chuỗi con chung dài nhất bằng mảng hậu tố. .... 47
Hình 3-26. Mơ hình kết chuỗi con của Yi. Lin ........................................... 51
Hình 3-27. Cây thứ bậc của quá trình phân đoạn theo phƣơng pháp của Yi.
Lin................................................................................................................ 53
Hình 4-1. Mơ hình bài tốn kết chuỗi con chung dài nhất .......................... 55
Hình 4-2. Giao diện ứng dụng trong nhóm 1: dữ liệu đầu vào ................... 57
Hình 4-3. Giao diện ứng dụng trong nhóm 2: dữ liệu đầu ra ...................... 58
Hình 4-4. Kết quả đạt đƣợc trên bộ dữ liệu Currency với ratio = 10, số
Break_Point = 5. .......................................................................................... 60
Hình 4-5. Kết quả đạt đƣợc trên bộ dữ liệu Wafer với ratio = 10, số
Break_Point = 18. ........................................................................................ 62
Hình 4-6. Kết quả đạt đƣợc trên bộ dữ liệu ECG5000 với ratio = 10, số
Break_Point = 16. ........................................................................................ 64
Hình 4-7. Kết quả đạt đƣợc trên bộ dữ liệu LSF5 và LSF6 với ratio = 10,
số Break_Point = 14. ................................................................................... 66
Hình 4-8. Kết quả đạt đƣợc trên bộ dữ liệu LightCurve với ratio = 10, số
Break_Point = 12. ........................................................................................ 68


x

DANH SÁCH BẢNG

Bảng 2.1. Bảng thống kê dùng để tra những điểm ngắt theo phân bố Gauss
với số vùng phân bố từ 3 đến 10. ([5]) ........................................................ 15
Bảng 3.1. Các hậu tố của chuỗi s = banana. ................................................ 46
Bảng 4.1. Các tập dữ liệu đƣợc sử dụng trong luận văn này. ..................... 56
Bảng 4.2. Bảng mô tả chức năng các thành phần trong giao diện nhóm 1. 57
Bảng 4.3. Bảng mô tả chức năng các thành phần trong giao diện nhóm 2. 58
Bảng 4.4. Thơng tin về hai bộ dữ liệu Currency và các giá trị đầu vào dùng
để ký hiệu hóa chuỗi dữ liệu thời gian. ....................................................... 59
Bảng 4.5. Kết quả thực nghiệm tìm chuỗi con tƣơng quan nhất trên tập dữ
liệu Currency. .............................................................................................. 59
Bảng 4.6. Thông tin về hai bộ dữ liệu Wafer và các giá trị đầu vào dùng để
ký hiệu hóa chuỗi dữ liệu thời gian. ............................................................ 61
Bảng 4.7. Kết quả thực nghiệm tìm chuỗi con tƣơng quan nhất trên tập dữ
liệu Wafer. ................................................................................................... 61
Bảng 4.8. Thông tin về hai bộ dữ liệu ECG5000 và các giá trị đầu vào dùng
để ký hiệu hóa chuỗi dữ liệu thời gian. ....................................................... 63
Bảng 4.9. Kết quả thực nghiệm tìm chuỗi con tƣơng quan nhất trên tập dữ
liệu ECG5000. ............................................................................................. 63
Bảng 4.10. Thông tin về hai bộ dữ liệu LSF và các giá trị đầu vào dùng để
ký hiệu hóa chuỗi dữ liệu thời gian. ............................................................ 65
Bảng 4.11. Kết quả thực nghiệm tìm chuỗi con tƣơng quan nhất trên tập dữ
liệu LSF5 và LSF6. ..................................................................................... 65
Bảng 4.12. Thông tin về hai bộ dữ liệu LightCurve và các giá trị đầu vào
dùng để ký hiệu hóa chuỗi dữ liệu thời gian. .............................................. 67
Bảng 4.13. Kết quả thực nghiệm tìm chuỗi con tƣơng quan nhất trên tập dữ
liệu LightCurve. ........................................................................................... 67
Bảng 4.14. Kết quả thực nghiệm trên tập dữ liệu Currency ........................ 70
Bảng 4.15. Kết quả thực nghiệm trên tập dữ liệu Wafer............................. 72
Bảng 4.16. Kết quả thực nghiệm trên tập dữ liệu ECG5000....................... 73
Bảng 4.17. Kết quả thực nghiệm trên tập dữ liệu LSF5 và LSF6 ............... 74

Bảng 4.18. Kết quả thực nghiệm trên tập dữ liệu LightCurve .................... 76
Bảng 4.19. Kết quả thực nghiệm trên 5 tập dữ liệu với giải thuật Jocor ..... 77


1

CHƢƠNG 1 GIỚI THIỆU TỔNG QUAN ĐỀ TÀI
Chƣơng đầu gồm ba phần:
Phần thứ nhất khái quát một số khái niệm cơ bản liên quan đến đề tài nhƣ:
dữ liệu chuỗi thời gian và bài toán kết chuỗi con trên dữ liệu chuỗi thời gian. Phần
thứ hai giới thiệu sơ lƣợc mục tiêu, nội dung nghiên cứu chính của đề tài và những
kết quả đạt đƣợc. Phần cuối chƣơng trình bày tổng quan cấu trúc bố cục luận văn.

1.1 Giới thiệu đề tài
1.1.1 Dữ liệu chuỗi thời gian
Trong thời đại ngày nay, khi con ngƣời sống trong một xã hội hiện đại với
sự phát triển cao của công nghệ thông tin cùng với việc ra đời và phát triển của
máy tính số, tất cả mọi thông tin mà con ngƣời dùng để phục vụ cuộc sống đã
đƣợc số hố tồn bộ. Chúng đƣợc chuyển thể thành các đối tƣợng dữ liệu có ý
nghĩa và lƣu trữ trên máy tính. Các đối tƣợng dữ liệu này tồn tại trong rất nhiều
ứng dụng thực tế đã đƣợc xây dựng và phát triển qua các thập kỹ nhƣ: y tế, giáo
dục, địa lý, sinh học phân tử, văn bản, hình ảnh hoặc đoạn phim. Trong đó, các
ứng dụng khai phá dữ liệu chuỗi thời gian (time series data mining) chiếm một vị
trí quan trọng. Các giải thuật khai phá dữ liệu chuỗi thời gian thƣờng có chi phí rất
lớn về thời gian thực thi và tài nguyên bộ nhớ. Do đó việc nghiên cứu các phƣơng
pháp hiệu quả để khai phá các dữ liệu chuỗi thời gian rất quan trọng và thu hút rất
nhiều sự quan tâm.
Đã có nhiều tác giả đƣa ra khái niệm về dữ liệu chuỗi thời gian nhƣng phần
lớn đều thống nhất dữ liệu chuỗi thời gian (time series data) là tập hợp các giá trị
đƣợc quan sát trong những thời điểm cách đều nhau. Đối tƣợng dữ liệu có thể có

hai hay nhiều chiều nhƣng trong đó phải có một chiều là thời gian. Ví dụ nhƣ: số
đo điện tâm đồ (Hình 1-1), mực nƣớc, dữ liệu đo đƣợc từ các bộ cảm biến về thời
tiết và môi trƣờng nhƣ độ ẩm, áp suất khơng khí, lƣu lƣợng truyền trên mạng hoặc


2
trong lĩnh vực kinh tế, tài chính nhƣ: giá cả thị trƣờng chứng khoán, doanh số sản
phẩm, tỷ lệ lãi suất trên thị trƣờng, v.v…
Dữ liệu chuỗi thời gian thƣờng có kích thƣớc rất lớn và gia tăng nhanh vì
đƣợc đo đạc liên tục trong thời gian dài.

Hình 1-1. Dữ liệu chuỗi thời gian điện tâm đồ
1.1.2 Bài toán kết chuỗi con trên chuỗi dữ liệu thời gian
Có hai cách định nghĩa bài toán kết chuỗi con (Subsequence join) trên dữ
liệu chuỗi thời gian.
Định nghĩa 1: kết chuỗi con là tìm các cặp chuỗi con tƣơng tự nhau trong
hai chuỗi thời gian dài. Hai chuỗi dữ liệu thời gian có thể đƣợc kết hợp tại bất kỳ
vị trí nào và có chiều dài tuỳ ý. Kết quả minh hoạ của việc kết chuỗi con trên hai
chuỗi dữ liệu thời gian (Hình 1-2) [23].

Hình 1-2. Hai chuỗi dữ liệu thời gian đã được kết hợp để hiển thị một số
cặp chuỗi con khớp nhau


3
Định nghĩa 2: Kết chuỗi con là kết hai chuỗi dữ liệu thời gian vào trong
một phân đoạn tƣơng quan nhất về độ trễ và khoảng thời gian, việc này cung cấp
những thơng tin hữu ích về việc đồng bộ của chuỗi dữ liệu thời gian [18]. Ví dụ:
(Hình 1-3) thể hiện tỷ giá hối đoái của hai đồng Indian Rupee (INR) và Singapore
Dollar (SGD) so với đồng USA từ năm 1966.

Trong luận văn này, chúng tôi sử dụng định nghĩa 2 của bài tốn kết chuỗi
con.

Hình 1-3. Hai chuỗi dữ liệu thời gian của tỷ giá hối đoái tiền tệ được kết
hợp để cho thấy mối tương quan cao trong quá khứ. Trục x hiển thị ngày làm
việc. trục y hiển thị tỷ lệ chuyển đổi của INR và SGD so với USD sau khi bình
thường hố.
Kết chuỗi con là bài toán xử lý trên dữ liệu chuỗi thời gian đã có nhiều
nghiên cứu trong những năm gần đây. Một trong những khó khăn lớn nhất giải
quyết bài tốn là chi phí khơng gian bộ nhớ lớn, thời gian xử lý lâu nếu tiếp cận
bằng phƣơng pháp cửa sổ trƣợt (sliding window) thuần tuý.
Có hai cách tiếp cận phổ biến hiện nay là lập chỉ mục (indexing) và giải
thuật lặp lồng nhau (nested loop join). Các cách tiếp cận trên hiện nay đa phần chỉ
giải quyết trên dữ liệu ngoại tuyến (offline/ static data). Bài toán trở nên phức tạp
hơn nếu ứng dụng xử lý dữ liệu luồng (streaming data).


4

1.2

Mục tiêu và nhiệm vụ của đề tài
Mục tiêu nghiên cứu bài toán kết chuỗi con trên dữ liệu chuỗi thời gian tập

trung vào các vấn đề sau:
 Nghiên cứu cây hậu tố, mảng hậu tố, xử lý song song trên mảng hậu tố và các
vấn đề liên quan.
 Nghiên cứu bài toán kết chuỗi con trên dữ liệu chuỗi thời gian.
 Nghiên cứu các kỹ thuật thu giảm số chiều và rời rạc hóa dữ liệu chuỗi thời
gian.

Kết hợp các nghiên cứu ở trên để kết chuỗi con trên dữ liệu chuỗi thời gian dựa
vào việc tìm chuỗi con chung dài nhất bằng cây hậu tố với một số cải tiến đƣợc đề
xuất nhằm làm giảm độ phức tạp tính tốn đồng thời làm tăng độ chính xác của kết
quả sau khi kết chuỗi con.

1.3 Phƣơng pháp nghiên cứu
Để giải quyết bài toán kết chuỗi con trên chuỗi dữ liệu thời gian, chúng tôi
đề xuất giải pháp sử dụng cây hậu tố để tìm chuỗi con tƣơng quan nhất của hai
chuỗi thời gian. Xem xét những thành quả của các cơng trình liên quan, rút ra
những kết luận, những thơng tin hữu ích cho đề tài.

1.4 Ý nghĩa của luận văn
Hiện nay có khá nhiều giải thuật để giải quyết bài toán kết chuỗi con. Các
phƣơng pháp thƣờng dùng là phƣơng pháp kết trực tiếp, phƣơng pháp lập chỉ mục
trên dữ liệu chuỗi thời gian(Indexing), phƣơng pháp phân đoạn khơng đồng nhất.
Tuy nhiên cịn có các hạn chế về thời gian xử lý và truy vấn. Do đó luận văn đi tìm
một cách tiếp cận khác dựa vào phƣơng pháp tìm chuỗi con chung dài nhất của hai
chuỗi ký tự bằng cây hậu tố để kết chuỗi con trên chuỗi dữ liệu thời gian.

1.5 Những kết quả đạt đƣợc của luận văn
Trong thời gian giới hạn làm luận văn, chúng tơi đã hiện thực hệ thống tìm
chuỗi con chung dài nhất của hai chuỗi dữ liệu thời gian, gồm 5 thành phần chính
nhƣ sau: phần tiền xử lý dữ liệu, phần rời rạc hóa chuỗi dữ liệu thời gian, phần các


5
giải thuật tìm chuỗi con chung dài nhất, phần hậu kiểm và phần trực quan hóa dữ
liệu.
Trong phần thứ nhất, từ hai chuỗi dữ liệu ban đầu sau khi đã đƣợc chuẩn
hóa và sử dụng phép biến đổi thu giảm số chiều PAA chúng tơi rút trích ra các

chuỗi con từ hai tập dữ liệu đã đƣợc thu giảm đó và tạo thành hai tập dữ liệu các
chuỗi con.
Trong phần thứ hai, chúng tôi thực hiện phƣơng pháp rời rạc hóa dữ liệu
SAX từ hai tập dữ liệu đã thu giảm số chiều PAA trong phần thứ nhất.
Trong phần thứ ba, chúng tơi hiện thực các giải thuật tìm chuỗi con chung
dài nhất dựa trên kết quả đạt đƣợc của phép biến đổi SAX bằng cây hậu tố, mảng
hậu tố và xử lý song song trên mảng hậu tố.
Trong phần thứ tƣ, chúng tôi dựa trên kết quả chuỗi con chung dài nhất tìm
đƣợc trong phần thứ ba để hậu kiểm bằng phƣơng pháp kết dựa trên hệ số tƣơng
quan (giải thuật Jocor)[18].
Phần cuối cùng, chúng tơi trực quan hóa kết quả thu đƣợc.
Hệ thống của chúng tôi chạy thực nghiệm trên năm cặp dữ liệu chuỗi thời
gian mẫu để đánh giá và so sánh hiệu quả giữa các giải thuật tìm chuỗi con chung
dài nhất (cây hậu tố, mảng hậu tố, xử lý song song trên mảng hậu tố). Qua thực
nghiệm, kết quả cho thấy việc áp dụng bài toán phát hiện chuỗi con chung dài nhất
của hai chuỗi ký tự dựa vào cây hậu tố, mảng hậu tố và xử lý song song trên mảng
hậu tố vào công tác tìm phân đoạn tƣơng quan với nhau nhất trên hai chuỗi thời
gian là rất hiệu quả và có độ phức tạp tính tốn thấp.

1.6 Bố cục luận văn
Luận văn đƣợc chia làm các phần chính nhƣ sau:
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 cũng nhƣ giới thiệu các định nghĩa, các vấn đề có liên quan
nhƣ: dữ liệu chuỗi thời gian, bài toán kết chuỗi con, mục tiêu nghiên cứu đề tài,
phƣơng pháp nghiên cứu, những kết quả đạt đƣợc và bố cục của luận văn.


6
CHƢƠNG 2 CƠ SỞ LÝ THUYẾT: Chƣơng này trình bày chi tiết về các cơ
sở lý thuyết đƣợc áp dụng trong đề tài nhƣ: độ đo khoảng cách, các công trình về

biểu diễn chuỗi thời gian, chuỗi thời gian, chuỗi con và sơ sở lý thuyết về lập trình
song song trên hệ thống đa nhân (multi core).
CHƢƠNG 3 CÁC CÔNG TRÌNH LIÊN QUAN: Chƣơng này trình bày sơ
lƣợc về các cơng trình có liên quan đến bài tốn kết chuỗi con trên dữ liệu chuỗi
thời gian, chi tiết về cây hậu tố, mảng hậu tố và cách tiếp cận xử lý song song trên
mảng hậu tố.
CHƢƠNG 4 PHƢƠNG PHÁP ĐỀ NGHỊ VÀ THỰC NGHIỆM: Phần đầu
chƣơng này khái quát bài tốn kết chuỗi con và đƣa ra mơ hình giải quyết bài toán
kết chuỗi con. Phần sau chƣơng này tiến hành thực nghiệm: thực nghiệm về bài
toán kết chuỗi con, thực nghiệm so sánh hai giải thuật cây hậu tố, mảng hậu tố, xử
lý song song trên mảng hậu tố và hậu kiểm bằng độ tƣơng quan của chuỗi con
tƣơng quan nhất.
CHƢƠNG 5 TỔNG KẾT: Chƣơng này trình bày tổng lƣợc lại toàn bộ nội
dung quan trọng của luận văn, các đóng góp chính của đề tài và hƣớng phát triển.
TÀI LIỆU THAM KHẢO.


7

CHƢƠNG 2 CƠ SỞ LÝ THUYẾT
Phần đầu của chƣơng sẽ trình bày những cơng trình về độ đo khoảng cách
trong chuỗi thời gian nhƣ: độ đo khoảng cách Minkowski và độ đo xoắn thời gian
động.
Phần thứ hai trình bày những cơng trình liên quan đến thao tác truy vấn
chuỗi thời gian, liên quan đến bài toán kết chuỗi con nhƣ phƣơng pháp xấp xỉ gộp
từng đoạn (PAA) để thu giảm số chiều và phƣơng pháp Phép xấp xỉ gộp ký hiệu
hóa (SAX) để rời rạc hóa chuỗi thời gian trƣớc khi thực hiện thao tác kết chuỗi
con, một số cơ sở lý thuyết về chuỗi thời gian và chuỗi con cũng đƣợc giới thiệu
trong chƣơng này.


2.1 Độ đo khoảng cách
Phần này điểm qua một số nghiên cứu nhằm đƣa ra cách đánh giá về độ đo
khoảng cách. Cho đến hiện tại, nhiều tác giả đã đề nghị nhiều độ đo khoảng cách
khác nhau. Mỗi độ đo khoảng cách sẽ thích hợp với từng ứng dụng cụ thể.
Vấn đề quan trọng nhất của bài tốn tìm kiếm tƣơng tự là cách tính khoảng
cách của hai đối tƣợng Oi, Oj. Trong trƣờng hợp hai đối tƣợng này giống nhau thì
khoảng cách này sẽ là 0 và ngƣợc lại chúng càng khác nhau thì khoảng cách càng
lớn. Để có thể tính tốn và so sánh thì các khoảng cách này đƣợc biểu diễn thành
các số thực.
Độ đo khoảng cách giữa cách đối tƣợng nên thỏa các tính chất sau:
1. D(x, y) = 0 nếu và chỉ nếu x = y
2. D(x, y) = D(y, x)
3. D(x, y) ≥ 0 với mọi x, y
4. D(x, y) < D(x, z) + D(y, z)


8
Độ đo khoảng cách có ý nghĩa quan trọng trong bài toán so trùng trên dữ
liệu chuỗi thời gian, đặc biệt là trong các mơ hình có dùng trích xuất đặc trƣng hay
thu giảm số chiều. Gọi Xf, Yf là biểu diễn của X, Y sau khi trích xuất đặc trƣng hay
thu giảm số chiều, độ đo khoảng cách D phải đảm bảo: D(Xf, Yf) ≤ D(X, Y).
Trong tài liệu này, độ đo khoảng cách đƣợc định nghĩa trên hai chuỗi thời
gian có chiều dài bằng nhau X, Y và đƣợc ký hiệu Sim(X, Y) [1]. Sau đây là những
phƣơng pháp đánh giá độ tƣơng tự đã đƣợc một số tác giả đề nghị:
2.1.1 Độ đo Minkowski
Hầu hết các công trình đều dựa trên độ đo khoảng cách này. Khoảng cách
Minkowski đƣợc định nghĩa nhƣ sau:
n

)  p  ( xi  yi ) p trong đó p=1.. 


(

i 1

Tuy p có thể có nhiều giá trị khác nhau nhƣng trong các nghiên cứu p
thƣờng nhận
(
{

)
(

)
(

)

Một số ƣu điểm và nhƣợc điểm của phƣơng pháp này:
 Ƣu điểm:
 Quá trình tính tốn đơn giản và dễ dàng.
 Phù hợp khi sử dụng các biến đổi DWT, PAA, SAX (các phƣơng pháp biến
đổi này sẽ đƣợc trình bày bên dƣới của chƣơng).
 Nhƣợc điểm:
 Nhạy cảm với nhiễu.
 Không hiệu quả với dữ liệu đƣợc đo ở nhiều thang đo khác nhau.


9
2.1.2 Độ đo xoắn thời gian động

Độ đo xoắn thời gian động (Dynamic Time Warping – DTW) tƣơng tự
cách tính khoảng cách Minkowski nhƣng thay vì so trùng hai đƣờng biểu diễn dữ
liệu bằng cách tính khoảng cách từng cặp điểm 1 - 1 (điểm thứ i của chuỗi thứ nhất
so với điểm thứ i của chuỗi thứ hai) thì một điểm có thể ánh xạ với nhiều điểm và
ánh xạ này khơng thẳng hàng. (Hình 2-1) minh họa cách ánh xạ điểm trong độ đo
xoắn thời gian động so với độ đo Euclid. Cách tính khoảng cách xoắn thời gian
động sẽ đƣợc trình bày chi tiết trong chƣơng cơ sở lý thuyết của đề tài.

Hình 2-1. Cách ánh xạ cặp điểm của độ đo Euclid và độ đo DTW (nguồn
[17])
Một số ƣu điểm và nhƣợc điểm của phƣơng pháp này:
 Ƣu điểm:
 Phƣơng pháp DWT cho phép nhận dạng những mẫu có hình dạng giống
nhau nhƣng chiều dài hình dạng về mặt thời gian có thể khác nhau.
 Phƣơng pháp DWT thì hiệu quả hơn rất nhiều so với phƣơng pháp tính
khoảng cách theo Euclid. Đặt biệt trong các bài toán phân loại
(classfication), gom cụm (clustering) hay trong các các ứng dụng nhận dạng
giọng nói.
 Nhƣợc điểm:
 Nhƣợc điểm lớn nhất của DTW là thời gian chạy rất lâu, độ phức tạp là
O(wn), trong đó w là chiều dài cửa sổ xoắn, n là chiều dài chuỗi.


10

2.2 Các cơng trình về biểu diễn chuỗi thời gian
Vì dữ liệu chuỗi thời gian là rất lớn, không thể xử lý trong bộ nhớ chính mà
phải tốn nhiều lần truy cập đĩa ngồi, chi phí truy cập đĩa ngồi là rất đáng kể so
với chi phí tính tốn, thƣờng gây ra hiện tƣợng thắt cổ chai khi thực hiện các
nhiệm vụ khai phá dữ liệu. Do đó, nhiều phƣơng pháp xấp xỉ chuỗi thời gian đƣợc

đề xuất để có thể dễ dàng xử lý trong bộ nhớ chính và giảm thiểu số lần truy cập
đĩa ngoài. Những phƣơng pháp này thƣờng đƣợc gọi là những kỹ thuật thu giảm số
chiều (dimensionality reduction). Một số phƣơng pháp vừa thu giảm số chiều vừa
rời rạc hóa dữ liệu chuỗi thời gian đƣợc gọi là phƣơng pháp rời rạc hóa
(discretization) và phƣơng pháp tổng quát để thu giảm số chiều có thể tóm tắt nhƣ
sau:
 Thiết lập một độ đo khoảng cách d (hay cịn gọi là hàm tính khoảng cách,
thƣờng dùng là hàm tính khoảng cách Euclid).
 Thiết kế một kỹ thuật thu giảm số chiều để rút trích một đặc trƣng có chiều dài
k (tức là một đặc trƣng gồm k giá trị), với k có thể đƣợc xử lý một cách hữu
hiệu nhờ một cấu trúc chỉ mục không gian (đa chiều).
 Cung cấp một độ đo khoảng cách dk trên không gian đặc trƣng k chiều trên và
chứng tỏ rằng nó thỏa điều kiện chặn dƣới sau:
dk(X’, Y’) ≤ d(X, Y)
Điều kiện chặn dƣới nhƣ trên có nghĩa là hàm khoảng cách tính trên khơng
gian đặc trƣng (hay không gian thu giảm) của hai chuỗi thời gian đã đƣợc biến đổi
X’, Y’ từ hai chuỗi ban đầu X, Y phải chặn dƣới khoảng cách thật của chúng trên
không gian nguyên thủy, điều này đảm bảo không xảy ra false dismissal (những
đối tƣợng thỏa điều kiện nhƣng bị bỏ sót).
Sau đây là một số phƣơng pháp biểu diễn cụ thể.
2.2.1 Phƣơng pháp xấp xỉ gộp từng đoạn (PAA)
Phƣơng pháp xấp xỉ gộp từng đoạn PAA (Piecewise Aggregate
Approximation), do Keogh và các cộng sự đề xuất năm 2001 [3], tuần tự xấp xỉ k


11
giá trị liền kề nhau thành một giá trị, là giá trị trung bình cộng của k giá trị đó. Quá
trình bắt đầu từ đầu chuỗi thời gian đến cuối chuỗi. Kết quả của phép biến đổi là
đƣờng thẳng có dạng bậc thang (Hình 2-2). Cho


(với j = 1,…,n)

là một chuỗi dữ liệu thời gian sẽ đƣợc thu giảm về một chuỗi con
̅ ̅

̅

̅̅̅ ( với i = 1,…,w), biết rằng w là số chiều thu giảm của nó đƣợc tính

theo cơng thức sau:

̅

∑

(

([5])

)

Hình 2-2. Phương pháp biểu diễn PAA với n = 128, w=8 ([5])
Phƣơng pháp PAA rất trực quan và đơn giản trong tính tốn nhƣng nó đã
đƣợc chứng minh là rất hữu hiệu, thích hợp và hỗ trợ các phƣơng pháp tính
khoảng cách khác nhƣ: khoảng cách Euclid, DTW, Minkowski. Ngoài ra, một
phƣơng pháp đo khoảng cách đƣợc đề xuất nhƣ sau trên không gian thu giảm số
chiều sau khi qua phép biến đổi PAA:
(̅
Trong đó ̅


̅

chuỗi dữ liệu thời gian

̅

̅(

̅)

√ √∑

(̅

̅) ([5])

) là hai chuỗi biến đổi xấp xỉ của hai

. Phƣơng pháp này không phụ thuộc vào cấu trúc chỉ

mục cụ thể nào, có thể sử dụng F-index, R-tree…


12
 Ƣu điểm:
 Thời gian tính tốn nhanh và dễ dàng.
 Hỗ trợ câu truy vấn có chiều dài khác nhau.
 Hàm khoảng cách đƣợc đề nghị có giá trị chặn dƣới chặt so với dữ liệu gốc.
 Nhƣợc điểm:
 Xây dựng lại chuỗi ban đầu khó và thƣờng sinh lỗi lớn, trong khi các

phƣơng pháp trên có cơng thức để tái tạo lại chuỗi ban đầu với tỉ lệ lỗi nhỏ.
 Không quan tâm đến những điểm đặc biệt khác nhƣ điểm giá trị nhỏ nhất,
lớn nhất của mỗi đoạn xấp xỉ.
2.2.2 Phép xấp xỉ gộp ký hiệu hóa SAX
Phƣơng pháp xấp xỉ gộp ký hiệu hóa SAX (Symbolic Aggregate
Approximation), do Lin và các cộng sự đề xuất năm 2003 [5], đƣợc xây dựng dựa
trên phƣơng pháp thu giảm số chiều PAA và giả sử dữ liệu thu giảm số chiều đã
đƣợc chuẩn hóa theo trung bình zero và độ lệch chuẩn một. Dữ liệu ban đầu đƣợc
chia thành từng đoạn dùng phƣơng pháp PAA. Sau đó, ánh xạ từng đoạn này thành
các ký tự rời rạc. Vì khơng gian thu giảm là không gian các ký tự, nên khơng thể
sử dụng các hàm tính khoảng cách nhận đối số là các giá trị thực mà cần có cơ chế
ánh xạ sự khác biệt giữa hai ký tự thành giá trị số. Phƣơng pháp SAX sử dụng hàm
tính khoảng cách MINDIST [5] trên không gian thu giảm, thỏa điều kiện chặn
dƣới. Phƣơng pháp lập chỉ mục đƣợc sử dụng là phƣơng pháp tập tin xấp xỉ hóa
vector (Vector Approximation File), ngồi ra có thể sử dụng R-tree và các kỹ thuật
lập chỉ mục cho chuỗi ký tự cổ điển nhƣ cây hậu tố (suffix tree). Để biến đổi theo
SAX, ta thực hiện các bƣớc sau:
2.2.2.1 Chuẩn hóa dữ liệu
Do tập dữ liệu ban đầu có thể có nguồn gốc khác nhau nên miền giá trị của
dữ liệu cũng sẽ khác nhau đƣợc gọi là dữ liệu thô (raw data). Dữ liệu thơ sẽ có
những giá trị khơng phù hợp với miền trị dữ liệu đƣợc gọi là giá trị nhiễu (noise
values). Trong nhiều trƣờng hợp, dữ liệu nhiễu có thể làm sai lệch kết quả cuối
cùng. Thậm chí tỷ lệ lỗi và sai sót có thể tăng lên gấp đôi nếu ứng dụng không